ebab7d0da53c51438720d60c6e2e467c - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Euclidean algorithm</title>

</head>

Euclidean algorithm

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">This article is about an algorithm for the greatest common divisor. For the mathematics of space, see <a href="Euclidean_geometry" title="Euclidean geometry">Euclidean geometry</a>. For other uses of "Euclidean", see <a href="Euclidean_(disambiguation)" class="mw-redirect mw-disambig" title="Euclidean (disambiguation)">Euclidean (disambiguation)</a>.</div>

<div role="note" class="hatnote navigation-not-searchable">Not to be confused with <a href="Euclidean_division" title="Euclidean division">Euclidean division</a>.</div>

In <a href="Mathematics" title="Mathematics">mathematics</a>, the Euclidean algorithm,<a href="#cite_note-1">[note 1]</a> or Euclid's algorithm, is an efficient method for computing the <a href="Greatest_common_divisor" title="Greatest common divisor">greatest common divisor</a> (GCD) of two <a href="Integers" class="mw-redirect" title="Integers">integers</a>, the largest number that divides them both without a <a href="Remainder" title="Remainder">remainder</a>. It is named after the ancient Greek <a href="Mathematician" title="Mathematician">mathematician</a> <a href="Euclid" title="Euclid">Euclid</a>, who first described it in <a href="Euclid's_Elements" title="Euclid's Elements">his Elements</a> (<abbr title="circa">c.</abbr> 300 BC).

It is an example of an <a href="Algorithm" title="Algorithm">algorithm</a>, and is one of the oldest algorithms in common use. It can be used to reduce <a href="Fraction_(mathematics)" class="mw-redirect" title="Fraction (mathematics)">fractions</a> to their <a href="Irreducible_fraction" title="Irreducible fraction">simplest form</a>, and is a part of many other number-theoretic and cryptographic calculations.

The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example, 21 is the GCD of 252 and 105 (as 252 = 21 × 12 and 105 = 21 × 5), and the same number 21 is also the GCD of 105 and 252 − 105 = 147. Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, that number is the GCD of the original two numbers. By <a href="#Bézout's_identity">reversing the steps</a> or using the <a href="Extended_Euclidean_algorithm" title="Extended Euclidean algorithm">extended Euclidean algorithm</a>, the GCD can be expressed as a <a href="Linear_combination" title="Linear combination">linear combination</a> of the two original numbers, that is the sum of the two numbers, each multiplied by an <a href="Integer" title="Integer">integer</a> (for example, 21 = 5 × 105 + (−2) × 252). The fact that the GCD can always be expressed in this way is known as <a href="B%C3%A9zout's_identity" title="Bézout's identity">Bézout's identity</a>.

The version of the Euclidean algorithm described above—which follows Euclid's original presentation—may require many subtraction steps to find the GCD when one of the given numbers is much bigger than the other. A more efficient version of the algorithm shortcuts these steps, instead replacing the larger of the two numbers by its remainder when divided by the smaller of the two (with this version, the algorithm stops when reaching a zero remainder). With this improvement, the algorithm never requires more steps than five times the number of digits (base 10) of the smaller integer. This was proven by <a href="Gabriel_Lam%C3%A9" title="Gabriel Lamé">Gabriel Lamé</a> in 1844 (<a href="Lam%C3%A9%E2%80%99s_Theorem" class="mw-redirect" title="Lamé’s Theorem">Lamé's Theorem</a>),<a href="#cite_note-2">[1]</a><a href="#cite_note-3">[2]</a> and marks the beginning of <a href="Computational_complexity_theory" title="Computational complexity theory">computational complexity theory</a>. Additional methods for improving the algorithm's efficiency were developed in the 20th century.

The Euclidean algorithm has many theoretical and practical applications. It is used for reducing <a href="Fraction_(mathematics)" class="mw-redirect" title="Fraction (mathematics)">fractions</a> to their <a href="Irreducible_fraction" title="Irreducible fraction">simplest form</a> and for performing <a href="Division_(mathematics)" title="Division (mathematics)">division</a> in <a href="Modular_arithmetic" title="Modular arithmetic">modular arithmetic</a>. Computations using this algorithm form part of the <a href="Cryptographic_protocol" title="Cryptographic protocol">cryptographic protocols</a> that are used to secure <a href="Internet" title="Internet">internet</a> communications, and in methods for breaking these cryptosystems by <a href="Integer_factorization" title="Integer factorization">factoring large composite numbers</a>. The Euclidean algorithm may be used to solve <a href="Diophantine_equation" title="Diophantine equation">Diophantine equations</a>, such as finding numbers that satisfy multiple congruences according to the <a href="Chinese_remainder_theorem" title="Chinese remainder theorem">Chinese remainder theorem</a>, to construct <a href="Simple_continued_fraction" title="Simple continued fraction">continued fractions</a>, and to find accurate <a href="Diophantine_approximation" title="Diophantine approximation">rational approximations</a> to real numbers. Finally, it can be used as a basic tool for proving theorems in <a href="Number_theory" title="Number theory">number theory</a> such as <a href="Lagrange's_four-square_theorem" title="Lagrange's four-square theorem">Lagrange's four-square theorem</a> and the <a href="Fundamental_theorem_of_arithmetic" title="Fundamental theorem of arithmetic">uniqueness of prime factorizations</a>.

The original algorithm was described only for natural numbers and geometric lengths (real numbers), but the algorithm was generalized in the 19th century to other types of numbers, such as <a href="Gaussian_integer" title="Gaussian integer">Gaussian integers</a> and <a href="Polynomial" title="Polynomial">polynomials</a> of one variable. This led to modern <a href="Abstract_algebra" title="Abstract algebra">abstract algebraic</a> notions such as <a href="Euclidean_domain" title="Euclidean domain">Euclidean domains</a>.

<div class="mw-heading mw-heading2"><h2 id="Background:_greatest_common_divisor">Background: greatest common divisor</h2></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Greatest_common_divisor" title="Greatest common divisor">Greatest common divisor</a></div>

The Euclidean algorithm calculates the greatest common divisor (GCD) of two <a href="Natural_number" title="Natural number">natural numbers</a> a and b. The greatest common divisor g is the largest natural number that divides both a and b without leaving a remainder. Synonyms for GCD include greatest common factor (GCF), highest common factor (HCF), highest common divisor (HCD), and greatest common measure (GCM). The greatest common divisor is often written as gcd(a, b) or, more simply, as (a, b),<a href="#cite_note-4">[3]</a> although the latter notation is ambiguous, also used for concepts such as an <a href="Ideal_(ring_theory)" title="Ideal (ring theory)">ideal</a> in the <a href="Ring_of_integers" title="Ring of integers">ring of integers</a>, which is closely related to GCD.

If gcd(a, b) = 1, then a and b are said to be <a href="Coprime_integers" title="Coprime integers">coprime</a> (or relatively prime).<a href="#cite_note-5">[4]</a> This property does not imply that a or b are themselves <a href="Prime_number" title="Prime number">prime numbers</a>.<a href="#cite_note-6">[5]</a> For example, 6 and 35 factor as 6 = 2 × 3 and 35 = 5 × 7, so they are not prime, but their prime factors are different, so 6 and 35 are coprime, with no common factors other than 1.

Let g = gcd(a, b). Since a and b are both multiples of g, they can be written a = mg and b = ng, and there is no larger number G > g for which this is true. The natural numbers m and n must be coprime, since any common factor could be factored out of m and n to make g greater. Thus, any other number c that divides both a and b must also divide g. The greatest common divisor g of a and b is the unique (positive) common divisor of a and b that is divisible by any other common divisor c.<a href="#cite_note-7">[6]</a>

The greatest common divisor can be visualized as follows.<a href="#cite_note-8">[7]</a> Consider a rectangular area a by b, and any common divisor c that divides both a and b exactly. The sides of the rectangle can be divided into segments of length c, which divides the rectangle into a grid of squares of side length c. The GCD g is the largest value of c for which this is possible. For illustration, a 24×60 rectangular area can be divided into a grid of: 1×1 squares, 2×2 squares, 3×3 squares, 4×4 squares, 6×6 squares or 12×12 squares. Therefore, 12 is the GCD of 24 and 60. A 24×60 rectangular area can be divided into a grid of 12×12 squares, with two squares along one edge (24/12 = 2) and five squares along the other (60/12 = 5).

The greatest common divisor of two numbers a and b is the product of the prime factors shared by the two numbers, where each prime factor can be repeated as many times as it divides both a and b.<a href="#cite_note-Schroeder_21-9">[8]</a> For example, since 1386 can be factored into 2 × 3 × 3 × 7 × 11, and 3213 can be factored into 3 × 3 × 3 × 7 × 17, the GCD of 1386 and 3213 equals 63 = 3 × 3 × 7, the product of their shared prime factors (with 3 repeated since 3 × 3 divides both). If two numbers have no common prime factors, their GCD is 1 (obtained here as an instance of the <a href="Empty_product" title="Empty product">empty product</a>); in other words, they are coprime. A key advantage of the Euclidean algorithm is that it can find the GCD efficiently without having to compute the prime factors.<a href="#cite_note-10">[9]</a><a href="#cite_note-11">[10]</a> <a href="Integer_factorization" title="Integer factorization">Factorization</a> of large integers is believed to be a computationally very difficult problem, and the security of many widely used <a href="Cryptographic_protocol" title="Cryptographic protocol">cryptographic protocols</a> is based upon its infeasibility.<a href="#cite_note-Schroeder_216-12">[11]</a>

Another definition of the GCD is helpful in advanced mathematics, particularly <a href="Ring_theory" title="Ring theory">ring theory</a>.<a href="#cite_note-Leveque_p33-13">[12]</a> The greatest common divisor g of two nonzero numbers a and b is also their smallest positive integral linear combination, that is, the smallest positive number of the form ua + vb where u and v are integers. The set of all integral linear combinations of a and b is actually the same as the set of all multiples of g (mg, where m is an integer). In modern mathematical language, the <a href="Ideal_(ring_theory)" title="Ideal (ring theory)">ideal</a> generated by a and b is the ideal generated by g alone (an ideal generated by a single element is called a <a href="Principal_ideal" title="Principal ideal">principal ideal</a>, and all ideals of the integers are principal ideals). Some properties of the GCD are in fact easier to see with this description, for instance the fact that any common divisor of a and b also divides the GCD (it divides both terms of ua + vb). The equivalence of this GCD definition with the other definitions is described below.

The GCD of three or more numbers equals the product of the prime factors common to all the numbers,<a href="#cite_note-14">[13]</a> but it can also be calculated by repeatedly taking the GCDs of pairs of numbers.<a href="#cite_note-15">[14]</a> For example,

Thus, Euclid's algorithm, which computes the GCD of two integers, suffices to calculate the GCD of arbitrarily many integers.

<div class="mw-heading mw-heading3"><h3 id="Procedure">Procedure</h3></div>

<div class="euclidean-algorithm-steps calculator-container calculatorgadget-enabled" style="border: 1px solid #a2a9b1; background-color: var(--background-color-neutral-subtle, #f8f9fa); color: inherit; margin: 0.5em 0 0.5em 1em; padding: 0.5em; float: right; clear: right; font-size: 88%; line-height: 1.5em; width: 22em; display:none;" data-calculator-refresh-on-load="true">Compute the Euclidean algorithm step by step

/* start https://en.wikipedia.org/ */

.mw-parser-output .calculator-hideifzero.calculator-value-false{display:none}

/* end https://en.wikipedia.org/ */

</style>a = 1071; b = 462

a = <span class="calculator-field" data-calculator-type="plain" style="background-color: light-dark( hsl(55,100%,70%,var(--calculator-colorstep0)), hsl(55,100%,25%,var(--calculator-colorstep0)) ); color: inherit" data-calculator-formula="r0" data-calculator-size="4">119; b = <span class="calculator-field" data-calculator-type="plain" style="background-color: light-dark( hsl(155,100%,70%,var(--calculator-colorstep0)), hsl(155,100%,25%,var(--calculator-colorstep0)) ); color: inherit" data-calculator-formula="r1" data-calculator-size="4">61

-1<div role="log">

<span class="calculator-field calculator-hideifzero calculator-value-false texhtml" data-calculator-type="passthru" data-calculator-formula="ifgreaterorequal(curstep,0,1,0)" data-calculator-aria-live="polite" data-calculator-aria-atomic="true"> = q0 × + r0 <span class="calculator-field calculator-hideifzero calculator-value-false texhtml" data-calculator-type="passthru" data-calculator-formula="ifgreaterorequal(curstep,1,1,0)" data-calculator-aria-live="polite" data-calculator-aria-atomic="true">q0 = ; r0 = Since r0 = 0 the algorithm is finished. Thus GCD( , ) = .<span class="calculator-field calculator-hideifzero calculator-value-false texhtml" data-calculator-type="passthru" data-calculator-formula="ifgreaterorequal(curstep,2,1,0)" data-calculator-aria-live="polite" data-calculator-aria-atomic="true"><hr> = q1 × + r1 <span class="calculator-field calculator-hideifzero calculator-value-false texhtml" data-calculator-type="passthru" data-calculator-formula="ifgreaterorequal(curstep,3,1,0)" data-calculator-aria-live="polite" data-calculator-aria-atomic="true">q1 = ; r1 = Since r1 = 0 the algorithm is finished. Thus GCD( , ) = .<span class="calculator-field calculator-hideifzero calculator-value-false texhtml" data-calculator-type="passthru" data-calculator-formula="ifgreaterorequal(curstep,4,1,0)" data-calculator-aria-live="polite" data-calculator-aria-atomic="true"><hr> = q2 × + r2 <span class="calculator-field calculator-hideifzero calculator-value-false texhtml" data-calculator-type="passthru" data-calculator-formula="ifgreaterorequal(curstep,5,1,0)" data-calculator-aria-live="polite" data-calculator-aria-atomic="true">q2 = ; r2 = Since r2 = 0 the algorithm is finished. Thus GCD( , ) = .<span class="calculator-field calculator-hideifzero calculator-value-false texhtml" data-calculator-type="passthru" data-calculator-formula="ifgreaterorequal(curstep,6,1,0)" data-calculator-aria-live="polite" data-calculator-aria-atomic="true"><hr> = q3 × + r3 <span class="calculator-field calculator-hideifzero calculator-value-false texhtml" data-calculator-type="passthru" data-calculator-formula="ifgreaterorequal(curstep,7,1,0)" data-calculator-aria-live="polite" data-calculator-aria-atomic="true">q3 = ; r3 = Since r3 = 0 the algorithm is finished. Thus GCD( , ) = .<span class="calculator-field calculator-hideifzero calculator-value-false texhtml" data-calculator-type="passthru" data-calculator-formula="ifgreaterorequal(curstep,8,1,0)" data-calculator-aria-live="polite" data-calculator-aria-atomic="true"><hr> = q4 × + r4 <span class="calculator-field calculator-hideifzero calculator-value-false texhtml" data-calculator-type="passthru" data-calculator-formula="ifgreaterorequal(curstep,9,1,0)" data-calculator-aria-live="polite" data-calculator-aria-atomic="true">q4 = ; r4 = Since r4 = 0 the algorithm is finished. Thus GCD( , ) = .<span class="calculator-field calculator-hideifzero calculator-value-false texhtml" data-calculator-type="passthru" data-calculator-formula="ifgreaterorequal(curstep,10,1,0)" data-calculator-aria-live="polite" data-calculator-aria-atomic="true"><hr> = q5 × + r5 <span class="calculator-field calculator-hideifzero calculator-value-false texhtml" data-calculator-type="passthru" data-calculator-formula="ifgreaterorequal(curstep,11,1,0)" data-calculator-aria-live="polite" data-calculator-aria-atomic="true">q5 = ; r5 = Since r5 = 0 the algorithm is finished. Thus GCD( , ) = .<span class="calculator-field calculator-hideifzero calculator-value-false texhtml" data-calculator-type="passthru" data-calculator-formula="ifgreaterorequal(curstep,12,1,0)" data-calculator-aria-live="polite" data-calculator-aria-atomic="true"><hr> = q6 × + r6 <span class="calculator-field calculator-hideifzero calculator-value-false texhtml" data-calculator-type="passthru" data-calculator-formula="ifgreaterorequal(curstep,13,1,0)" data-calculator-aria-live="polite" data-calculator-aria-atomic="true">q6 = ; r6 = Since r6 = 0 the algorithm is finished. Thus GCD( , ) = .<span class="calculator-field calculator-hideifzero calculator-value-false texhtml" data-calculator-type="passthru" data-calculator-formula="ifgreaterorequal(curstep,14,1,0)" data-calculator-aria-live="polite" data-calculator-aria-atomic="true"><hr> = q7 × + r7 <span class="calculator-field calculator-hideifzero calculator-value-false texhtml" data-calculator-type="passthru" data-calculator-formula="ifgreaterorequal(curstep,15,1,0)" data-calculator-aria-live="polite" data-calculator-aria-atomic="true">q7 = ; r7 = Since r7 = 0 the algorithm is finished. Thus GCD( , ) = .<span class="calculator-field calculator-hideifzero calculator-value-false texhtml" data-calculator-type="passthru" data-calculator-formula="ifgreaterorequal(curstep,16,1,0)" data-calculator-aria-live="polite" data-calculator-aria-atomic="true"><hr> = q8 × + r8 <span class="calculator-field calculator-hideifzero calculator-value-false texhtml" data-calculator-type="passthru" data-calculator-formula="ifgreaterorequal(curstep,17,1,0)" data-calculator-aria-live="polite" data-calculator-aria-atomic="true">q8 = ; r8 = Since r8 = 0 the algorithm is finished. Thus GCD( , ) = .<span class="calculator-field calculator-hideifzero calculator-value-false texhtml" data-calculator-type="passthru" data-calculator-formula="ifgreaterorequal(curstep,18,1,0)" data-calculator-aria-live="polite" data-calculator-aria-atomic="true"><hr> = q9 × + r9 <span class="calculator-field calculator-hideifzero calculator-value-false texhtml" data-calculator-type="passthru" data-calculator-formula="ifgreaterorequal(curstep,19,1,0)" data-calculator-aria-live="polite" data-calculator-aria-atomic="true">q9 = ; r9 = Since r9 = 0 the algorithm is finished. Thus GCD( , ) = .<span class="calculator-field calculator-hideifzero calculator-value-false texhtml" data-calculator-type="passthru" data-calculator-formula="ifgreaterorequal(curstep,20,1,0)" data-calculator-aria-live="polite" data-calculator-aria-atomic="true"><hr> = q10 × + r10 <span class="calculator-field calculator-hideifzero calculator-value-false texhtml" data-calculator-type="passthru" data-calculator-formula="ifgreaterorequal(curstep,21,1,0)" data-calculator-aria-live="polite" data-calculator-aria-atomic="true">q10 = ; r10 = Since r10 = 0 the algorithm is finished. Thus GCD( , ) = .

Number is too big for the calculator</div>

Restart <span class="calculator-field calculator-hideifzero" data-calculator-type="passthru" data-calculator-formula="or( and( ifequal(curstep%2,0), ifless(curstep,21 ) ), and( ifbetween(curstep,-1,21), not( ifequal( index(r,(curstep-1)/2+2), 0 ) ), ifequal( curstep,1,r1,1 ) ) )"><span class="calculator-field-button cdx-button cdx-button--action-progressive cdx-button--weight-primary cdx-button--size-medium" style="cursor:pointer" data-calculator-for="curstep" data-calculator-formula="curstep+1">Start

</div>

The Euclidean algorithm can be thought of as constructing a sequence of non-negative integers that begins with the two given integers <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{-2}=a}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{-2}=a}</annotation>

</semantics>

</math><img src="./4b0136faf86219f470fb2e7ce19768e6cce4444d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.71ex; height:2.009ex;" alt="{\displaystyle r_{-2}=a}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{-1}=b}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{-1}=b}</annotation>

</semantics>

</math><img src="./6c050066bdeed7fdaabfe541629f843e6516e1e7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.477ex; height:2.509ex;" alt="{\displaystyle r_{-1}=b}" loading="lazy"> and will eventually terminate with the integer zero: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{r_{-2}=a,\ r_{-1}=b,\ r_{0},\ r_{1},\ \cdots ,\ r_{n-1},\ r_{n}=0\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{r_{-2}=a,\ r_{-1}=b,\ r_{0},\ r_{1},\ \cdots ,\ r_{n-1},\ r_{n}=0\}}</annotation>

</semantics>

</math><img src="./88b215f1f4abd9a17e40896b538e62df052900f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:45.798ex; height:2.843ex;" alt="{\displaystyle \{r_{-2}=a,\ r_{-1}=b,\ r_{0},\ r_{1},\ \cdots ,\ r_{n-1},\ r_{n}=0\}}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{k+1}<r_{k}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{k+1}<r_{k}}</annotation>

</semantics>

</math><img src="./0050bd8ca461f3a4281bfee17c22e13f42666d44.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.474ex; height:2.176ex;" alt="{\displaystyle r_{k+1}<r_{k}}" loading="lazy">. The integer <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{n-1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{n-1}}</annotation>

</semantics>

</math><img src="./1bb9423fd6766c31baf0369064fcf25ea2b1f584.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.368ex; height:2.009ex;" alt="{\displaystyle r_{n-1}}" loading="lazy"> will then be the GCD and we can state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{gcd}}(a,b)=r_{n-1}}">

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{gcd}}(a,b)=r_{n-1}}</annotation>

</semantics>

</math><img src="./96158621032c947e43bfb4c168d7ff905cd33caa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.024ex; height:2.843ex;" alt="{\displaystyle {\text{gcd}}(a,b)=r_{n-1}}" loading="lazy">. The algorithm indicates how to construct the intermediate remainders <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{k}}</annotation>

</semantics>

</math><img src="./9b28e0e640d099f3676330bd4f604ae15c37bb4f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.137ex; height:2.009ex;" alt="{\displaystyle r_{k}}" loading="lazy"> via <a href="Euclidean_division" title="Euclidean division">division-with-remainder</a> on the preceding pair <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (r_{k-2},\ r_{k-1})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (r_{k-2},\ r_{k-1})}</annotation>

</semantics>

</math><img src="./cd0040f143b057dfaec76c8060a58b9e3c19d52d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.9ex; height:2.843ex;" alt="{\displaystyle (r_{k-2},\ r_{k-1})}" loading="lazy"> by finding an integer quotient <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q_{k}}</annotation>

</semantics>

</math><img src="./f27215e46abcad60f100434d2c8003310580af95.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.126ex; height:2.009ex;" alt="{\displaystyle q_{k}}" loading="lazy"> so that:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{k-2}=q_{k}\cdot r_{k-1}+r_{k}{\text{, with }}\ r_{k-1}>r_{k}\geq 0.}</annotation>

</semantics>

</math><img src="./b5f11ad02814d92f80b7dc1c51417700678cd9c4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:41.649ex; height:2.509ex;" alt="{\displaystyle r_{k-2}=q_{k}\cdot r_{k-1}+r_{k}{\text{, with }}\ r_{k-1}>r_{k}\geq 0.}" loading="lazy"></dd></dl>

Because the sequence of non-negative integers <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{r_{k}\}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{r_{k}\}}</annotation>

</semantics>

</math><img src="./8b17ba8cd3cd568f36a3e47f2d0b1b318e5c2c9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.462ex; height:2.843ex;" alt="{\displaystyle \{r_{k}\}}" loading="lazy"> is strictly decreasing, it eventually <a href="Well-ordering_principle" title="Well-ordering principle">must terminate</a>. In other words, since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{k}\geq 0}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{k}\geq 0}</annotation>

</semantics>

</math><img src="./88bee94c4dd17b9202cc261159e77292e1a5d535.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.398ex; height:2.509ex;" alt="{\displaystyle r_{k}\geq 0}" loading="lazy"> for every <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">, and each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{k}}</annotation>

</semantics>

</math><img src="./9b28e0e640d099f3676330bd4f604ae15c37bb4f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.137ex; height:2.009ex;" alt="{\displaystyle r_{k}}" loading="lazy"> is an integer that is strictly smaller than the preceding <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{k-1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{k-1}}</annotation>

</semantics>

</math><img src="./2dbe2626d424eb6b58b44a40172092dc04b16928.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.238ex; height:2.009ex;" alt="{\displaystyle r_{k-1}}" loading="lazy">, there eventually cannot be a non-negative integer smaller than zero, and hence the algorithm must terminate. In fact, the algorithm will always terminate at the nth step with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{n}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{n}}</annotation>

</semantics>

</math><img src="./57784cdf7f49f2c46baad4eb7b6a7d5c14eb5fa4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.267ex; height:2.009ex;" alt="{\displaystyle r_{n}}" loading="lazy"> equal to zero.<a href="#cite_note-16">[15]</a>

To illustrate, suppose the GCD of 1071 and 462 is requested. The sequence is initially <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{r_{-2}=1071,\ r_{-1}=462\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{r_{-2}=1071,\ r_{-1}=462\}}</annotation>

</semantics>

</math><img src="./d13bb0c5e0679933d256a47f508d4520436a1293.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.036ex; height:2.843ex;" alt="{\displaystyle \{r_{-2}=1071,\ r_{-1}=462\}}" loading="lazy"> and in order to find <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{0}}</annotation>

</semantics>

</math><img src="./fb12fcfddb65e3d1e6a044215f6e833f0cd4337b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.103ex; height:2.009ex;" alt="{\displaystyle r_{0}}" loading="lazy">, we need to find integers <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q_{0}}</annotation>

</semantics>

</math><img src="./9d68d37de188ac61f0c0e3f31d5322d1c486f2f4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.091ex; height:2.009ex;" alt="{\displaystyle q_{0}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{0}<r_{-1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{0}<r_{-1}}</annotation>

</semantics>

</math><img src="./b9881df9fbb3f2e6f2c2ce60f80163ca9c1b79f0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.583ex; height:2.176ex;" alt="{\displaystyle r_{0}<r_{-1}}" loading="lazy"> such that:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1071=q_{0}\cdot 462+r_{0}}</annotation>

</semantics>

</math><img src="./134fcdcde86566150a6ea0c4a67edcfa009a104d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:19.949ex; height:2.509ex;" alt="{\displaystyle 1071=q_{0}\cdot 462+r_{0}}" loading="lazy">.</dd></dl>

This is the quotient <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q_{0}=2}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q_{0}=2}</annotation>

</semantics>

</math><img src="./01aeacf38388c22735226bf7984fa4e0421567a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.352ex; height:2.509ex;" alt="{\displaystyle q_{0}=2}" loading="lazy"> since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1071=2\cdot 462+147}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1071=2\cdot 462+147}</annotation>

</semantics>

</math><img src="./94c999621b3352671d75af5a38849325a1eb48aa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:20.405ex; height:2.343ex;" alt="{\displaystyle 1071=2\cdot 462+147}" loading="lazy">. This determines <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{0}=147}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{0}=147}</annotation>

</semantics>

</math><img src="./5b4e0635872f040ead64628f6a9e9f485f8b2233.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.689ex; height:2.509ex;" alt="{\displaystyle r_{0}=147}" loading="lazy"> and so the sequence is now <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{1071,\ 462,\ r_{0}=147\}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{1071,\ 462,\ r_{0}=147\}}</annotation>

</semantics>

</math><img src="./cdd3b0efd9b16dc223104d6e041f3afba0c06837.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.38ex; height:2.843ex;" alt="{\displaystyle \{1071,\ 462,\ r_{0}=147\}}" loading="lazy">. The next step is to continue the sequence to find <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{1}}</annotation>

</semantics>

</math><img src="./ea214f2b31fb3869344bb9311da41c5cc38a99e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.103ex; height:2.009ex;" alt="{\displaystyle r_{1}}" loading="lazy"> by finding integers <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q_{1}}</annotation>

</semantics>

</math><img src="./9daa41f6e8f78ea6bb5711d7ac97901ce564b94e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.091ex; height:2.009ex;" alt="{\displaystyle q_{1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{1}<r_{0}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{1}<r_{0}}</annotation>

</semantics>

</math><img src="./b12c3a286a4d3bb52192f55f84a19d8fd9ddcf15.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.304ex; height:2.176ex;" alt="{\displaystyle r_{1}<r_{0}}" loading="lazy"> such that:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 462=q_{1}\cdot 147+r_{1}}</annotation>

</semantics>

</math><img src="./eb18f88782e8818d4e16a2ac2ac794be65812ddc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:18.787ex; height:2.509ex;" alt="{\displaystyle 462=q_{1}\cdot 147+r_{1}}" loading="lazy">.</dd></dl>

This is the quotient <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q_{1}=3}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q_{1}=3}</annotation>

</semantics>

</math><img src="./b2a6116e2c4a858aaf540d51e4e66f7ffd71910e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.352ex; height:2.509ex;" alt="{\displaystyle q_{1}=3}" loading="lazy"> since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 462=3\cdot 147+21}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 462=3\cdot 147+21}</annotation>

</semantics>

</math><img src="./e8dd01e2e052d1e21527bf9cf2ccaa137ad088e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:18.08ex; height:2.343ex;" alt="{\displaystyle 462=3\cdot 147+21}" loading="lazy">. This determines <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{1}=21}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{1}=21}</annotation>

</semantics>

</math><img src="./d76ce06c8842f345132606a468f41bfc181ce02b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.526ex; height:2.509ex;" alt="{\displaystyle r_{1}=21}" loading="lazy"> and so the sequence is now <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{1071,\ 462,\ 147,\ r_{1}=21\}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{1071,\ 462,\ 147,\ r_{1}=21\}}</annotation>

</semantics>

</math><img src="./377419d7664d8d9ab5a3fe736161190b9d4a14d9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.319ex; height:2.843ex;" alt="{\displaystyle \{1071,\ 462,\ 147,\ r_{1}=21\}}" loading="lazy">. The next step is to continue the sequence to find <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{2}}</annotation>

</semantics>

</math><img src="./4cbe9b0b294fdd6fadbf9a7249813f016dcbc44f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.103ex; height:2.009ex;" alt="{\displaystyle r_{2}}" loading="lazy"> by finding integers <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q_{2}}</annotation>

</semantics>

</math><img src="./fd2d05084feb02b8ba29b0673440fb673b102589.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.091ex; height:2.009ex;" alt="{\displaystyle q_{2}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{2}<r_{1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{2}<r_{1}}</annotation>

</semantics>

</math><img src="./0d285ffc35d03cc59b9248ef1aba3aca1db3c1e2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.304ex; height:2.176ex;" alt="{\displaystyle r_{2}<r_{1}}" loading="lazy"> such that:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 147=q_{2}\cdot 21+r_{2}}</annotation>

</semantics>

</math><img src="./00aa855c57184d1893bbadf26f03fe81af5f58c1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:17.624ex; height:2.509ex;" alt="{\displaystyle 147=q_{2}\cdot 21+r_{2}}" loading="lazy">.</dd></dl>

This is the quotient <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q_{2}=7}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q_{2}=7}</annotation>

</semantics>

</math><img src="./b9cedb62a43694c72c63d5111ec2abf553acca77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.352ex; height:2.509ex;" alt="{\displaystyle q_{2}=7}" loading="lazy"> since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 147=7\cdot 21+0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 147=7\cdot 21+0}</annotation>

</semantics>

</math><img src="./42e87dc6e6fe5d1f6423040fd2da30926e37a486.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:15.755ex; height:2.343ex;" alt="{\displaystyle 147=7\cdot 21+0}" loading="lazy">. This determines <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{2}=0}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{2}=0}</annotation>

</semantics>

</math><img src="./72f6b52dcbeb88769147b35e6edd21b698301547.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.364ex; height:2.509ex;" alt="{\displaystyle r_{2}=0}" loading="lazy"> and so the sequence is completed as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{1071,\ 462,\ 147,\ 21,\ r_{2}=0\}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{1071,\ 462,\ 147,\ 21,\ r_{2}=0\}}</annotation>

</semantics>

</math><img src="./9bf735b01cff1ed6b55ce0abc98f8f2988905728.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.097ex; height:2.843ex;" alt="{\displaystyle \{1071,\ 462,\ 147,\ 21,\ r_{2}=0\}}" loading="lazy"> as no further non-negative integer smaller than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math><img src="./2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy"> can be found. The penultimate remainder <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 21}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 21}</annotation>

</semantics>

</math><img src="./77ebb9ccf6080ba5c9a6ea8973cb2f26c50211cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.325ex; height:2.176ex;" alt="{\displaystyle 21}" loading="lazy"> is therefore the requested GCD:

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{gcd}}(1071,\ 462)=21.}</annotation>

</semantics>

</math><img src="./cd300bc3002d80df5682f917dd715d459f8217cc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.119ex; height:2.843ex;" alt="{\displaystyle {\text{gcd}}(1071,\ 462)=21.}" loading="lazy"></dd></dl>

We can generalize slightly by dropping any ordering requirement on the initial two values <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy">. If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a=b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a=b}</annotation>

</semantics>

</math><img src="./1956b03d1314c7071ac1f45ed7b1e29422dcfcc4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.326ex; height:2.176ex;" alt="{\displaystyle a=b}" loading="lazy">, the algorithm may continue and trivially find that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{gcd}}(a,\ a)=a}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{gcd}}(a,\ a)=a}</annotation>

</semantics>

</math><img src="./fad3c75dee86381c3e7294b138cb04e32fe73783.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.699ex; height:2.843ex;" alt="{\displaystyle {\text{gcd}}(a,\ a)=a}" loading="lazy"> as the sequence of remainders will be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{a,\ a,\ 0\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{a,\ a,\ 0\}}</annotation>

</semantics>

</math><img src="./0dd9b227019fa9774e888298439ac8590061ed13.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.176ex; height:2.843ex;" alt="{\displaystyle \{a,\ a,\ 0\}}" loading="lazy">. If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a<b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a<b}</annotation>

</semantics>

</math><img src="./91a7698e4c7401bb321f97888b872b583a9e4642.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.326ex; height:2.176ex;" alt="{\displaystyle a<b}" loading="lazy">, then we can also continue since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\equiv 0\cdot b+a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\equiv 0\cdot b+a}</annotation>

</semantics>

</math><img src="./fc32682dc755734e0b01e1fc2e0cbb81e1b9e1b4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:12.238ex; height:2.343ex;" alt="{\displaystyle a\equiv 0\cdot b+a}" loading="lazy">, suggesting the next remainder should be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> itself, and the sequence is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{a,\ b,\ a,\ \cdots \}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{a,\ b,\ a,\ \cdots \}}</annotation>

</semantics>

</math><img src="./13e8ec985de11109fdd5ef818058b27c909f3222.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.736ex; height:2.843ex;" alt="{\displaystyle \{a,\ b,\ a,\ \cdots \}}" loading="lazy">. Normally, this would be invalid because it breaks the requirement <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{0}<r_{-1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{0}<r_{-1}}</annotation>

</semantics>

</math><img src="./b9881df9fbb3f2e6f2c2ce60f80163ca9c1b79f0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.583ex; height:2.176ex;" alt="{\displaystyle r_{0}<r_{-1}}" loading="lazy"> but now we have <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a<b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a<b}</annotation>

</semantics>

</math><img src="./91a7698e4c7401bb321f97888b872b583a9e4642.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.326ex; height:2.176ex;" alt="{\displaystyle a<b}" loading="lazy"> by construction, so the requirement is automatically satisfied and the Euclidean algorithm can continue as normal. Therefore, dropping any ordering between the first two integers does not affect the conclusion that the sequence must eventually terminate because the next remainder will always satisfy <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{0}<b}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{0}<b}</annotation>

</semantics>

</math><img src="./cee19f7a6468daf3449129c0da9cd74c60907870.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.199ex; height:2.509ex;" alt="{\displaystyle r_{0}<b}" loading="lazy"> and everything continues as above. The only modifications that need to be made are that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{k}<r_{k-1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{k}<r_{k-1}}</annotation>

</semantics>

</math><img src="./7fef79fa31424b1f2f75ab8680ce6c99967dd167.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.474ex; height:2.176ex;" alt="{\displaystyle r_{k}<r_{k-1}}" loading="lazy"> only for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\geq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k\geq 0}</annotation>

</semantics>

</math><img src="./79214ef55efadfb1d9c9b02252eb8a71cf6f8b6b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.472ex; height:2.343ex;" alt="{\displaystyle k\geq 0}" loading="lazy">, and that the sub-sequence of non-negative integers <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{r_{k-1}\}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{r_{k-1}\}}</annotation>

</semantics>

</math><img src="./9f241182d363fb5368558a99442e54504cb2a065.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.563ex; height:2.843ex;" alt="{\displaystyle \{r_{k-1}\}}" loading="lazy"> for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\geq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k\geq 0}</annotation>

</semantics>

</math><img src="./79214ef55efadfb1d9c9b02252eb8a71cf6f8b6b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.472ex; height:2.343ex;" alt="{\displaystyle k\geq 0}" loading="lazy"> is strictly decreasing, therefore excluding <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a=r_{-2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a=r_{-2}}</annotation>

</semantics>

</math><img src="./965ed3d75ce7948e5fe434ec6f79dcbaf252b119.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.71ex; height:2.009ex;" alt="{\displaystyle a=r_{-2}}" loading="lazy"> from both statements.

<div class="mw-heading mw-heading3"><h3 id="Proof_of_validity">Proof of validity</h3></div>

The validity of the Euclidean algorithm can be proven by a two-step argument.<a href="#cite_note-17">[16]</a> In the first step, the final nonzero remainder rN−1 is shown to divide both a and b. Since it is a common divisor, it must be less than or equal to the greatest common divisor g. In the second step, it is shown that any common divisor of a and b, including g, must divide rN−1; therefore, g must be less than or equal to rN−1. These two opposite inequalities imply rN−1 = g.

To demonstrate that rN−1 divides both a and b (the first step), rN−1 divides its predecessor rN−2

since the final remainder rN is zero. rN−1 also divides its next predecessor rN−3

because it divides both terms on the right-hand side of the equation. Iterating the same argument, rN−1 divides all the preceding remainders, including a and b. None of the preceding remainders rN−2, rN−3, etc. divide a and b, since they leave a remainder. Since rN−1 is a common divisor of a and b, rN−1 ≤ g.

In the second step, any natural number c that divides both a and b (in other words, any common divisor of a and b) divides the remainders rk. By definition, a and b can be written as multiples of c: a = mc and b = nc, where m and n are natural numbers. Therefore, c divides the initial remainder r0, since r0 = a − q0b = mc − q0nc = (m − q0n)c. An analogous argument shows that c also divides the subsequent remainders r1, r2, etc. Therefore, the greatest common divisor g must divide rN−1, which implies that g ≤ rN−1. Since the first part of the argument showed the reverse (rN−1 ≤ g), it follows that g = rN−1. Thus, g is the greatest common divisor of all the succeeding pairs:<a href="#cite_note-18">[17]</a><a href="#cite_note-Lovasz_2003-19">[18]</a>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g=\gcd(a,b)=\gcd(a,r_{0})=\gcd(r_{0},r_{1})=\dots =\gcd(r_{k-1},r_{k})=\dots =\gcd(r_{N-2},r_{N-1})=\gcd(r_{N-1},0)=r_{N-1}}</annotation>

</semantics>

</math><img src="./7e666e8ff40bc7eaeb875386098edb5306036a0c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:109.098ex; height:2.843ex;" alt="{\displaystyle g=\gcd(a,b)=\gcd(a,r_{0})=\gcd(r_{0},r_{1})=\dots =\gcd(r_{k-1},r_{k})=\dots =\gcd(r_{N-2},r_{N-1})=\gcd(r_{N-1},0)=r_{N-1}}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Worked_example">Worked example</h3></div>

For illustration, the Euclidean algorithm can be used to find the greatest common divisor of a = 1071 and b = 462. To begin, multiples of 462 are subtracted from 1071 until the remainder is less than 462. Two such multiples can be subtracted (q0 = 2), leaving a remainder of 147:

Then multiples of 147 are subtracted from 462 until the remainder is less than 147. Three multiples can be subtracted (q1 = 3), leaving a remainder of 21:

Then multiples of 21 are subtracted from 147 until the remainder is less than 21. Seven multiples can be subtracted (q2 = 7), leaving no remainder:

Since the last remainder is zero, the algorithm ends with 21 as the greatest common divisor of 1071 and 462. This agrees with the gcd(1071, 462) found by prime factorization <a href="#Background:_greatest_common_divisor">above</a>. In tabular form, the steps are:

<th>Equation</th>

<th>Quotient and remainder

</th></tr>

<tr>

<td>q0 = 2 and r0 = 147

</td></tr>

<tr>

<td>q1 = 3 and r1 = 21

</td></tr>

<tr>

<td>q2 = 7 and r2 = 0; algorithm ends

</td></tr></tbody></table>

<div class="mw-heading mw-heading3"><h3 id="Visualization">Visualization</h3></div>

The Euclidean algorithm can be visualized in terms of the tiling analogy given above for the greatest common divisor.<a href="#cite_note-Kimberling_1983-20">[19]</a> Assume that we wish to cover an a×b rectangle with square tiles exactly, where a is the larger of the two numbers. We first attempt to tile the rectangle using b×b square tiles; however, this leaves an r0×b residual rectangle untiled, where r0 < b. We then attempt to tile the residual rectangle with r0×r0 square tiles. This leaves a second residual rectangle r1×r0, which we attempt to tile using r1×r1 square tiles, and so on. The sequence ends when there is no residual rectangle, i.e., when the square tiles cover the previous residual rectangle exactly. The length of the sides of the smallest square tile is the GCD of the dimensions of the original rectangle. For example, the smallest square tile in the adjacent figure is 21×21 (shown in red), and 21 is the GCD of 1071 and 462, the dimensions of the original rectangle (shown in green).

<div class="mw-heading mw-heading3"><h3 id="Euclidean_division">Euclidean division</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Euclidean_division" title="Euclidean division">Euclidean division</a></div>

At every step k, the Euclidean algorithm computes a quotient qk and remainder rk from two numbers rk−1 and rk−2

where the rk is non-negative and is strictly less than the <a href="Absolute_value" title="Absolute value">absolute value</a> of rk−1. The theorem which underlies the definition of the <a href="Euclidean_division" title="Euclidean division">Euclidean division</a> ensures that such a quotient and remainder always exist and are unique.<a href="#cite_note-21">[20]</a>

In Euclid's original version of the algorithm, the quotient and remainder are found by repeated subtraction; that is, rk−1 is subtracted from rk−2 repeatedly until the remainder rk is smaller than rk−1. After that rk and rk−1 are exchanged and the process is iterated. Euclidean division reduces all the steps between two exchanges into a single step, which is thus more efficient. Moreover, the quotients are not needed, thus one may replace Euclidean division by the <a href="Modulo_operation" class="mw-redirect" title="Modulo operation">modulo operation</a>, which gives only the remainder. Thus the iteration of the Euclidean algorithm becomes simply

<div class="mw-heading mw-heading3"><h3 id="Implementations">Implementations</h3></div>

Implementations of the algorithm may be expressed in <a href="Pseudocode" title="Pseudocode">pseudocode</a>. For example, the division-based version may be <a href="Computer_programming" title="Computer programming">programmed</a> as<a href="#cite_note-22">[21]</a>

<pre>function gcd(a, b)

while b ≠ 0

t := b

b := a mod b

a := t

return a

</pre>

At the beginning of the kth iteration, the variable b holds the latest remainder rk−1, whereas the variable a holds its predecessor, rk−2. The step b := a mod b is equivalent to the above recursion formula rk ≡ rk−2 mod rk−1. The <a href="Temporary_variable" title="Temporary variable">temporary variable</a> t holds the value of rk−1 while the next remainder rk is being calculated. At the end of the loop iteration, the variable b holds the remainder rk, whereas the variable a holds its predecessor, rk−1.

(If negative inputs are allowed, or if the <code>mod</code> function may return negative values, the last line must be replaced with <code>return abs(a)</code>.)

In the subtraction-based version, which was Euclid's original version, the remainder calculation (<code>b := a mod b</code>) is replaced by repeated subtraction.<a href="#cite_note-23">[22]</a> Contrary to the division-based version, which works with arbitrary integers as input, the subtraction-based version supposes that the input consists of positive integers and stops when a = b:

<pre>function gcd(a, b)

while a ≠ b

if a > b

a := a − b

else

b := b − a

return a

</pre>

The variables a and b alternate holding the previous remainders rk−1 and rk−2. Assume that a is larger than b at the beginning of an iteration; then a equals rk−2, since rk−2 > rk−1. During the loop iteration, a is reduced by multiples of the previous remainder b until a is smaller than b. Then a is the next remainder rk. Then b is reduced by multiples of a until it is again smaller than a, giving the next remainder rk+1, and so on.

The recursive version<a href="#cite_note-24">[23]</a> is based on the equality of the GCDs of successive remainders and the stopping condition gcd(rN−1, 0) = rN−1.

<pre>function gcd(a, b)

if b = 0

return a

else

return gcd(b, a mod b)

</pre>

(As above, if negative inputs are allowed, or if the <code>mod</code> function may return negative values, the instruction <code>return a</code> must be replaced by <code>return max(a, −a)</code>.)

For illustration, the gcd(1071, 462) is calculated from the equivalent gcd(462, 1071 mod 462) = gcd(462, 147). The latter GCD is calculated from the gcd(147, 462 mod 147) = gcd(147, 21), which in turn is calculated from the gcd(21, 147 mod 21) = gcd(21, 0) = 21.

<div class="mw-heading mw-heading3"><h3 id="Method_of_least_absolute_remainders">Method of least absolute remainders</h3></div>

In another version of Euclid's algorithm, the quotient at each step is increased by one if the resulting negative remainder is smaller in magnitude than the typical positive remainder.<a href="#cite_note-Ore_least_abs_remainders-25">[24]</a><a href="#cite_note-Stewart_1964-26">[25]</a> Previously, the equation

assumed that |rk−1| > rk > 0. However, an alternative negative remainder ek can be computed:

if rk−1 > 0 or

if rk−1 < 0.

If rk is replaced by ek. when |ek| < |rk|, then one gets a variant of Euclidean algorithm such that

at each step.

<a href="Leopold_Kronecker" title="Leopold Kronecker">Leopold Kronecker</a> has shown that this version requires the fewest steps of any version of Euclid's algorithm.<a href="#cite_note-Ore_least_abs_remainders-25">[24]</a><a href="#cite_note-Stewart_1964-26">[25]</a> More generally, it has been proven that, for every input numbers a and b, the number of steps is minimal if and only if qk is chosen in order that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left|{\frac {r_{k+1}}{r_{k}}}\right|<{\frac {1}{\varphi }}\sim 0.618,}">

<mrow>

<mfrac>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mrow>

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left|{\frac {r_{k+1}}{r_{k}}}\right|<{\frac {1}{\varphi }}\sim 0.618,}</annotation>

</semantics>

</math><img src="./284616d6eabd3159aa6f2fbbb9800dae0b079bd1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:20.864ex; height:5.676ex;" alt="{\displaystyle \left|{\frac {r_{k+1}}{r_{k}}}\right|<{\frac {1}{\varphi }}\sim 0.618,}" loading="lazy"> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varphi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varphi }</annotation>

</semantics>

</math><img src="./33ee699558d09cf9d653f6351f9fda0b2f4aaa3e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.52ex; height:2.176ex;" alt="{\displaystyle \varphi }" loading="lazy"> is the <a href="Golden_ratio" title="Golden ratio">golden ratio</a>.<a href="#cite_note-27">[26]</a>

<div class="mw-heading mw-heading2"><h2 id="Historical_development">Historical development</h2></div>

The Euclidean algorithm is one of the oldest algorithms in common use.<a href="#cite_note-Knuth,_p._318-28">[27]</a> It appears in <a href="Euclid's_Elements" title="Euclid's Elements">Euclid's Elements</a> (c. 300 BC), specifically in Book 7 (Propositions 1–2) and Book 10 (Propositions 2–3). In Book 7, the algorithm is formulated for integers, whereas in Book 10, it is formulated for lengths of line segments. (In modern usage, one would say it was formulated there for <a href="Real_number" title="Real number">real numbers</a>. But lengths, areas, and volumes, represented as real numbers in modern usage, are not measured in the same units and there is no natural unit of length, area, or volume; the concept of real numbers was unknown at that time.) The latter algorithm is geometrical. The GCD of two lengths a and b corresponds to the greatest length g that measures a and b evenly; in other words, the lengths a and b are both integer multiples of the length g.

The algorithm was probably not discovered by <a href="Euclid" title="Euclid">Euclid</a>, who compiled results from earlier mathematicians in his Elements.<a href="#cite_note-Weil_1983-29">[28]</a><a href="#cite_note-Jones_1994-30">[29]</a> The mathematician and historian <a href="Bartel_Leendert_van_der_Waerden" title="Bartel Leendert van der Waerden">B. L. van der Waerden</a> suggests that Book VII derives from a textbook on <a href="Number_theory" title="Number theory">number theory</a> written by mathematicians in the school of <a href="Pythagoras" title="Pythagoras">Pythagoras</a>.<a href="#cite_note-van_der_Waerden_1954-31">[30]</a> The algorithm was probably known by <a href="Eudoxus_of_Cnidus" title="Eudoxus of Cnidus">Eudoxus of Cnidus</a> (about 375 BC).<a href="#cite_note-Knuth,_p._318-28">[27]</a><a href="#cite_note-32">[31]</a> The algorithm may even pre-date Eudoxus,<a href="#cite_note-33">[32]</a><a href="#cite_note-34">[33]</a> judging from the use of the technical term ἀνθυφαίρεσις (anthyphairesis, reciprocal subtraction) in works by Euclid and <a href="Aristotle" title="Aristotle">Aristotle</a>.<a href="#cite_note-35">[34]</a> Claude Brezinski, following remarks by <a href="Pappus_of_Alexandria" title="Pappus of Alexandria">Pappus of Alexandria</a>, credits the algorithm to <a href="Theaetetus_(mathematician)" title="Theaetetus (mathematician)">Theaetetus</a> (c. 417 – c. 369 BC).<a href="#cite_note-36">[35]</a>

Centuries later, Euclid's algorithm was discovered independently both in India and in China,<a href="#cite_note-Stillwell,_p._31-37">[36]</a> primarily to solve <a href="Diophantine_equation" title="Diophantine equation">Diophantine equations</a> that arose in astronomy and making accurate calendars. In the late 5th century, the Indian mathematician and astronomer <a href="Aryabhata" title="Aryabhata">Aryabhata</a> described the algorithm as the "pulverizer",<a href="#cite_note-Tattersall,_p._70-38">[37]</a> perhaps because of its effectiveness in solving Diophantine equations.<a href="#cite_note-39">[38]</a> Although a special case of the <a href="Chinese_remainder_theorem" title="Chinese remainder theorem">Chinese remainder theorem</a> had already been described in the Chinese book <a href="Sunzi_Suanjing" title="Sunzi Suanjing">Sunzi Suanjing</a>,<a href="#cite_note-40">[39]</a> the general solution was published by <a href="Qin_Jiushao" title="Qin Jiushao">Qin Jiushao</a> in his 1247 book Shushu Jiuzhang (數書九章 <a href="Mathematical_Treatise_in_Nine_Sections" title="Mathematical Treatise in Nine Sections">Mathematical Treatise in Nine Sections</a>).<a href="#cite_note-41">[40]</a> The Euclidean algorithm was first described numerically and popularized in Europe in the second edition of <a href="Claude_Gaspard_Bachet_de_M%C3%A9ziriac" class="mw-redirect" title="Claude Gaspard Bachet de Méziriac">Bachet's</a> Problèmes plaisants et délectables (Pleasant and enjoyable problems, 1624).<a href="#cite_note-Tattersall,_p._70-38">[37]</a> In Europe, it was likewise used to solve Diophantine equations and in developing <a href="Simple_continued_fraction" title="Simple continued fraction">continued fractions</a>. The <a href="Extended_Euclidean_algorithm" title="Extended Euclidean algorithm">extended Euclidean algorithm</a> was published by the English mathematician <a href="Nicholas_Saunderson" title="Nicholas Saunderson">Nicholas Saunderson</a>,<a href="#cite_note-42">[41]</a> who attributed it to <a href="Roger_Cotes" title="Roger Cotes">Roger Cotes</a> as a method for computing continued fractions efficiently.<a href="#cite_note-43">[42]</a>

In the 19th century, the Euclidean algorithm led to the development of new number systems, such as <a href="Gaussian_integer" title="Gaussian integer">Gaussian integers</a> and <a href="Eisenstein_integer" title="Eisenstein integer">Eisenstein integers</a>. In 1815, <a href="Carl_Friedrich_Gauss" title="Carl Friedrich Gauss">Carl Gauss</a> used the Euclidean algorithm to demonstrate unique factorization of <a href="Gaussian_integer" title="Gaussian integer">Gaussian integers</a>, although his work was first published in 1832.<a href="#cite_note-Gauss_1832-44">[43]</a> Gauss mentioned the algorithm in his <a href="Disquisitiones_Arithmeticae" title="Disquisitiones Arithmeticae">Disquisitiones Arithmeticae</a> (published 1801), but only as a method for <a href="Continued_fraction" title="Continued fraction">continued fractions</a>.<a href="#cite_note-Stillwell,_p._31-37">[36]</a> <a href="Peter_Gustav_Lejeune_Dirichlet" title="Peter Gustav Lejeune Dirichlet">Peter Gustav Lejeune Dirichlet</a> seems to have been the first to describe the Euclidean algorithm as the basis for much of number theory.<a href="#cite_note-45">[44]</a> Lejeune Dirichlet noted that many results of number theory, such as unique factorization, would hold true for any other system of numbers to which the Euclidean algorithm could be applied.<a href="#cite_note-46">[45]</a> Lejeune Dirichlet's lectures on number theory were edited and extended by <a href="Richard_Dedekind" title="Richard Dedekind">Richard Dedekind</a>, who used Euclid's algorithm to study <a href="Algebraic_integer" title="Algebraic integer">algebraic integers</a>, a new general type of number. For example, Dedekind was the first to prove <a href="Fermat's_theorem_on_sums_of_two_squares" title="Fermat's theorem on sums of two squares">Fermat's two-square theorem</a> using the unique factorization of Gaussian integers.<a href="#cite_note-47">[46]</a> Dedekind also defined the concept of a <a href="Euclidean_domain" title="Euclidean domain">Euclidean domain</a>, a number system in which a generalized version of the Euclidean algorithm can be defined (as described <a href="#Euclidean_domains">below</a>). In the closing decades of the 19th century, the Euclidean algorithm gradually became eclipsed by Dedekind's more general theory of <a href="Ideal_(ring_theory)" title="Ideal (ring theory)">ideals</a>.<a href="#cite_note-48">[47]</a>

"[The Euclidean algorithm] is the granddaddy of all algorithms, because it is the oldest nontrivial algorithm that has survived to the present day."

</td></tr>

<tr>

<td style="text-align: left;"><a href="Donald_Knuth" title="Donald Knuth">Donald Knuth</a>, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 2nd edition (1981), p. 318.

</td></tr></tbody></table>

Other applications of Euclid's algorithm were developed in the 19th century. In 1829, <a href="Jacques_Charles_Fran%C3%A7ois_Sturm" title="Jacques Charles François Sturm">Charles Sturm</a> showed that the algorithm was useful in the <a href="Sturm's_theorem" title="Sturm's theorem">Sturm chain</a> method for counting the real roots of polynomials in any given interval.<a href="#cite_note-49">[48]</a>

The Euclidean algorithm was the first <a href="Integer_relation_algorithm" title="Integer relation algorithm">integer relation algorithm</a>, which is a method for finding integer relations between commensurate real numbers. Several novel <a href="Integer_relation_algorithm" title="Integer relation algorithm">integer relation algorithms</a> have been developed, such as the algorithm of <a href="Helaman_Ferguson" title="Helaman Ferguson">Helaman Ferguson</a> and R.W. Forcade (1979)<a href="#cite_note-50">[49]</a> and the <a href="Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm" title="Lenstra–Lenstra–Lovász lattice basis reduction algorithm">LLL algorithm</a>.<a href="#cite_note-51">[50]</a><a href="#cite_note-52">[51]</a>

In 1969, Cole and Davie developed a two-player game based on the Euclidean algorithm, called The Game of Euclid,<a href="#cite_note-53">[52]</a> which has an optimal strategy.<a href="#cite_note-54">[53]</a> The players begin with two piles of a and b stones. The players take turns removing m multiples of the smaller pile from the larger. Thus, if the two piles consist of x and y stones, where x is larger than y, the next player can reduce the larger pile from x stones to x − my stones, as long as the latter is a nonnegative integer. The winner is the first player to reduce one pile to zero stones.<a href="#cite_note-55">[54]</a><a href="#cite_note-56">[55]</a>

<div class="mw-heading mw-heading2"><h2 id="Mathematical_applications">Mathematical applications</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Bézout's_identity">Bézout's identity</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="B%C3%A9zout's_identity" title="Bézout's identity">Bézout's identity</a></div>

Bézout's identity states that the greatest common divisor g of two integers a and b can be represented as a linear sum of the original two numbers a and b.<a href="#cite_note-57">[56]</a> In other words, it is always possible to find integers s and t such that g = sa + tb.<a href="#cite_note-58">[57]</a><a href="#cite_note-59">[58]</a>

The integers s and t can be calculated from the quotients q0, q1, etc. by reversing the order of equations in Euclid's algorithm.<a href="#cite_note-60">[59]</a> Beginning with the next-to-last equation, g can be expressed in terms of the quotient qN−1 and the two preceding remainders, rN−2 and rN−3:

Those two remainders can be likewise expressed in terms of their quotients and preceding remainders,

Substituting these formulae for rN−2 and rN−3 into the first equation yields g as a linear sum of the remainders rN−4 and rN−5. The process of substituting remainders by formulae involving their predecessors can be continued until the original numbers a and b are reached:

After all the remainders r0, r1, etc. have been substituted, the final equation expresses g as a linear sum of a and b, so that g = sa + tb.

The Euclidean algorithm, and thus Bézout's identity, can be generalized to the context of <a href="Euclidean_domain" title="Euclidean domain">Euclidean domains</a>.

<div class="mw-heading mw-heading3"><h3 id="Principal_ideals_and_related_problems">Principal ideals and related problems</h3></div>

Bézout's identity provides yet another definition of the greatest common divisor g of two numbers a and b.<a href="#cite_note-Leveque_p33-13">[12]</a> Consider the set of all numbers ua + vb, where u and v are any two integers. Since a and b are both divisible by g, every number in the set is divisible by g. In other words, every number of the set is an integer multiple of g. This is true for every common divisor of a and b. However, unlike other common divisors, the greatest common divisor is a member of the set; by Bézout's identity, choosing u = s and v = t gives g. A smaller common divisor cannot be a member of the set, since every member of the set must be divisible by g. Conversely, any multiple m of g can be obtained by choosing u = ms and v = mt, where s and t are the integers of Bézout's identity. This may be seen by multiplying Bézout's identity by m,

Therefore, the set of all numbers ua + vb is equivalent to the set of multiples m of g. In other words, the set of all possible sums of integer multiples of two numbers (a and b) is equivalent to the set of multiples of gcd(a, b). The GCD is said to be the generator of the <a href="Ideal_(ring_theory)" title="Ideal (ring theory)">ideal</a> of a and b. This GCD definition led to the modern <a href="Abstract_algebra" title="Abstract algebra">abstract algebraic</a> concepts of a <a href="Principal_ideal" title="Principal ideal">principal ideal</a> (an ideal generated by a single element) and a <a href="Principal_ideal_domain" title="Principal ideal domain">principal ideal domain</a> (a <a href="Domain_(ring_theory)" title="Domain (ring theory)">domain</a> in which every ideal is a principal ideal).

Certain problems can be solved using this result.<a href="#cite_note-61">[60]</a> For example, consider two measuring cups of volume a and b. By adding/subtracting u multiples of the first cup and v multiples of the second cup, any volume ua + vb can be measured out. These volumes are all multiples of g = gcd(a, b).

<div class="mw-heading mw-heading3"><h3 id="Extended_Euclidean_algorithm">Extended Euclidean algorithm</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Extended_Euclidean_algorithm" title="Extended Euclidean algorithm">Extended Euclidean algorithm</a></div>

The integers s and t of Bézout's identity can be computed efficiently using the <a href="Extended_Euclidean_algorithm" title="Extended Euclidean algorithm">extended Euclidean algorithm</a>. This extension adds two recursive equations to Euclid's algorithm<a href="#cite_note-62">[61]</a>

with the starting values

Using this recursion, Bézout's integers s and t are given by s = sN and t = tN, where N + 1 is the step on which the algorithm terminates with rN+1 = 0.

The validity of this approach can be shown by induction. Assume that the recursion formula is correct up to step k − 1 of the algorithm; in other words, assume that

for all j less than k. The kth step of the algorithm gives the equation

Since the recursion formula has been assumed to be correct for rk−2 and rk−1, they may be expressed in terms of the corresponding s and t variables

Rearranging this equation yields the recursion formula for step k, as required

<div class="mw-heading mw-heading3"><h3 id="Matrix_method">Matrix method</h3></div>

The integers s and t can also be found using an equivalent <a href="Matrix_(mathematics)" title="Matrix (mathematics)">matrix</a> method.<a href="#cite_note-Koshy_2002-63">[62]</a> The sequence of equations of Euclid's algorithm

<mtr>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}a&=q_{0}b+r_{0}\\b&=q_{1}r_{0}+r_{1}\\&\,\,\,\vdots \\r_{N-2}&=q_{N}r_{N-1}+0\end{aligned}}}</annotation>

</semantics>

</math><img src="./bb95dceee016c6715d26238fc6adfb8eec615c97.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.005ex; width:20.263ex; height:13.176ex;" alt="{\displaystyle {\begin{aligned}a&=q_{0}b+r_{0}\\b&=q_{1}r_{0}+r_{1}\\&\,\,\,\vdots \\r_{N-2}&=q_{N}r_{N-1}+0\end{aligned}}}" loading="lazy"></dd></dl>

can be written as a product of 2×2 quotient matrices multiplying a two-dimensional remainder vector

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mrow>

</mrow>

</munderover>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{pmatrix}a\\b\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}b\\r_{0}\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}q_{1}&1\\1&0\end{pmatrix}}{\begin{pmatrix}r_{0}\\r_{1}\end{pmatrix}}=\cdots =\prod _{i=0}^{N}{\begin{pmatrix}q_{i}&1\\1&0\end{pmatrix}}{\begin{pmatrix}r_{N-1}\\0\end{pmatrix}}\,.}</annotation>

</semantics>

</math><img src="./257eaf53f86665ef4e927000e9c285441ac40841.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:85.216ex; height:7.343ex;" alt="{\displaystyle {\begin{pmatrix}a\\b\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}b\\r_{0}\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}q_{1}&1\\1&0\end{pmatrix}}{\begin{pmatrix}r_{0}\\r_{1}\end{pmatrix}}=\cdots =\prod _{i=0}^{N}{\begin{pmatrix}q_{i}&1\\1&0\end{pmatrix}}{\begin{pmatrix}r_{N-1}\\0\end{pmatrix}}\,.}" loading="lazy"></dd></dl>

Let M represent the product of all the quotient matrices

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mrow>

</mrow>

</munderover>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {M} ={\begin{pmatrix}m_{11}&m_{12}\\m_{21}&m_{22}\end{pmatrix}}=\prod _{i=0}^{N}{\begin{pmatrix}q_{i}&1\\1&0\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}q_{1}&1\\1&0\end{pmatrix}}\cdots {\begin{pmatrix}q_{N}&1\\1&0\end{pmatrix}}\,.}</annotation>

</semantics>

</math><img src="./3825723fc0b1e3723a637c7f51507b73ba36cc17.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:73.428ex; height:7.343ex;" alt="{\displaystyle \mathbf {M} ={\begin{pmatrix}m_{11}&m_{12}\\m_{21}&m_{22}\end{pmatrix}}=\prod _{i=0}^{N}{\begin{pmatrix}q_{i}&1\\1&0\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}q_{1}&1\\1&0\end{pmatrix}}\cdots {\begin{pmatrix}q_{N}&1\\1&0\end{pmatrix}}\,.}" loading="lazy"></dd></dl>

This simplifies the Euclidean algorithm to the form

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{pmatrix}a\\b\end{pmatrix}}=\mathbf {M} {\begin{pmatrix}r_{N-1}\\0\end{pmatrix}}=\mathbf {M} {\begin{pmatrix}g\\0\end{pmatrix}}\,.}</annotation>

</semantics>

</math><img src="./7c5287400df82c95499e1c507d932d07c147c08d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:32.057ex; height:6.176ex;" alt="{\displaystyle {\begin{pmatrix}a\\b\end{pmatrix}}=\mathbf {M} {\begin{pmatrix}r_{N-1}\\0\end{pmatrix}}=\mathbf {M} {\begin{pmatrix}g\\0\end{pmatrix}}\,.}" loading="lazy"></dd></dl>

To express g as a linear sum of a and b, both sides of this equation can be multiplied by the <a href="Invertible_matrix" title="Invertible matrix">inverse</a> of the matrix M.<a href="#cite_note-Koshy_2002-63">[62]</a><a href="#cite_note-Bach_1996-64">[63]</a> The <a href="Determinant" title="Determinant">determinant</a> of M equals (−1)N+1, since it equals the product of the determinants of the quotient matrices, each of which is negative one. Since the determinant of M is never zero, the vector of the final remainders can be solved using the inverse of M

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<msup>

</mrow>

</msup>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{pmatrix}g\\0\end{pmatrix}}=\mathbf {M} ^{-1}{\begin{pmatrix}a\\b\end{pmatrix}}=(-1)^{N+1}{\begin{pmatrix}m_{22}&-m_{12}\\-m_{21}&m_{11}\end{pmatrix}}{\begin{pmatrix}a\\b\end{pmatrix}}\,.}</annotation>

</semantics>

</math><img src="./e9daccd9cfbe875345f40d5ce6c4807c8a463668.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:54.758ex; height:6.176ex;" alt="{\displaystyle {\begin{pmatrix}g\\0\end{pmatrix}}=\mathbf {M} ^{-1}{\begin{pmatrix}a\\b\end{pmatrix}}=(-1)^{N+1}{\begin{pmatrix}m_{22}&-m_{12}\\-m_{21}&m_{11}\end{pmatrix}}{\begin{pmatrix}a\\b\end{pmatrix}}\,.}" loading="lazy"></dd></dl>

Since the top equation gives

the two integers of Bézout's identity are s = (−1)N+1m22 and t = (−1)Nm12. The matrix method is as efficient as the equivalent recursion, with two multiplications and two additions per step of the Euclidean algorithm.

<div class="mw-heading mw-heading3"><h3 id="Euclid's_lemma_and_unique_factorization">Euclid's lemma and unique factorization</h3></div>

Bézout's identity is essential to many applications of Euclid's algorithm, such as demonstrating the <a href="Fundamental_theorem_of_arithmetic" title="Fundamental theorem of arithmetic">unique factorization</a> of numbers into prime factors.<a href="#cite_note-65">[64]</a> To illustrate this, suppose that a number L can be written as a product of two factors u and v, that is, L = uv. If another number w also divides L but is coprime with u, then w must divide v, by the following argument: If the greatest common divisor of u and w is 1, then integers s and t can be found such that

by Bézout's identity. Multiplying both sides by v gives the relation:

Since w divides both terms on the right-hand side, it must also divide the left-hand side, v. This result is known as <a href="Euclid's_lemma" title="Euclid's lemma">Euclid's lemma</a>.<a href="#cite_note-Ore,_p._44-66">[65]</a> Specifically, if a prime number divides L, then it must divide at least one factor of L. Conversely, if a number w is coprime to each of a series of numbers a1, a2, ..., an, then w is also coprime to their product, a1 × a2 × ... × an.<a href="#cite_note-Ore,_p._44-66">[65]</a>

Euclid's lemma suffices to prove that every number has a unique factorization into prime numbers.<a href="#cite_note-67">[66]</a> To see this, assume the contrary, that there are two independent factorizations of L into m and n prime factors, respectively

Since each prime p divides L by assumption, it must also divide one of the q factors; since each q is prime as well, it must be that p = q. Iteratively dividing by the p factors shows that each p has an equal counterpart q; the two prime factorizations are identical except for their order. The unique factorization of numbers into primes has many applications in mathematical proofs, as shown below.

<div class="mw-heading mw-heading3"><h3 id="Linear_Diophantine_equations">Linear Diophantine equations</h3></div>

<a href="Diophantine_equation" title="Diophantine equation">Diophantine equations</a> are equations in which the solutions are restricted to integers; they are named after the 3rd-century Alexandrian mathematician <a href="Diophantus" title="Diophantus">Diophantus</a>.<a href="#cite_note-68">[67]</a> A typical linear Diophantine equation seeks integers x and y such that<a href="#cite_note-69">[68]</a>

where a, b and c are given integers. This can be written as an equation for x in <a href="Modular_arithmetic" title="Modular arithmetic">modular arithmetic</a>:

Let g be the greatest common divisor of a and b. Both terms in ax + by are divisible by g; therefore, c must also be divisible by g, or the equation has no solutions. By dividing both sides by c/g, the equation can be reduced to Bezout's identity

where s and t can be found by the <a href="Extended_Euclidean_algorithm" title="Extended Euclidean algorithm">extended Euclidean algorithm</a>.<a href="#cite_note-70">[69]</a> This provides one solution to the Diophantine equation, x1 = s (c/g) and y1 = t (c/g).

In general, a linear Diophantine equation has no solutions, or an infinite number of solutions.<a href="#cite_note-71">[70]</a> To find the latter, consider two solutions, (x1, y1) and (x2, y2), where

or equivalently

Therefore, the smallest difference between two x solutions is b/g, whereas the smallest difference between two y solutions is a/g. Thus, the solutions may be expressed as

By allowing u to vary over all possible integers, an infinite family of solutions can be generated from a single solution (x1, y1). If the solutions are required to be positive integers (x > 0, y > 0), only a finite number of solutions may be possible. This restriction on the acceptable solutions allows some systems of Diophantine equations with more unknowns than equations to have a finite number of solutions;<a href="#cite_note-72">[71]</a> this is impossible for a <a href="System_of_linear_equations" title="System of linear equations">system of linear equations</a> when the solutions can be any <a href="Real_number" title="Real number">real number</a> (see <a href="Underdetermined_system" title="Underdetermined system">Underdetermined system</a>).

<div class="mw-heading mw-heading3"><h3 id="Multiplicative_inverses_and_the_RSA_algorithm">Multiplicative inverses and the RSA algorithm</h3></div>

A <a href="Finite_field" title="Finite field">finite field</a> is a set of numbers with four generalized operations. The operations are called addition, subtraction, multiplication and division and have their usual properties, such as <a href="Commutativity" class="mw-redirect" title="Commutativity">commutativity</a>, <a href="Associativity" class="mw-redirect" title="Associativity">associativity</a> and <a href="Distributivity" class="mw-redirect" title="Distributivity">distributivity</a>. An example of a finite field is the set of 13 numbers {0, 1, 2, ..., 12} using <a href="Modular_arithmetic" title="Modular arithmetic">modular arithmetic</a>. In this field, the results of any mathematical operation (addition, subtraction, multiplication, or division) is reduced <a href="Modulo_operation" class="mw-redirect" title="Modulo operation">modulo</a> 13; that is, multiples of 13 are added or subtracted until the result is brought within the range 0–12. For example, the result of 5 × 7 = 35 mod 13 = 9. Such finite fields can be defined for any prime p; using more sophisticated definitions, they can also be defined for any power m of a prime pm. Finite fields are often called <a href="%C3%89variste_Galois" title="Évariste Galois">Galois</a> fields, and are abbreviated as GF(p) or GF(pm).

In such a field with m numbers, every nonzero element a has a unique <a href="Modular_multiplicative_inverse" title="Modular multiplicative inverse">modular multiplicative inverse</a>, a−1 such that aa−1 = a−1a ≡ 1 mod m. This inverse can be found by solving the congruence equation ax ≡ 1 mod m,<a href="#cite_note-73">[72]</a> or the equivalent linear Diophantine equation<a href="#cite_note-74">[73]</a>

This equation can be solved by the Euclidean algorithm, as described <a href="#Linear_Diophantine_equations">above</a>. Finding multiplicative inverses is an essential step in the <a href="RSA_algorithm" class="mw-redirect" title="RSA algorithm">RSA algorithm</a>, which is widely used in <a href="Electronic_commerce" class="mw-redirect" title="Electronic commerce">electronic commerce</a>; specifically, the equation determines the integer used to decrypt the message.<a href="#cite_note-75">[74]</a> Although the RSA algorithm uses <a href="Ring_(mathematics)" title="Ring (mathematics)">rings</a> rather than fields, the Euclidean algorithm can still be used to find a multiplicative inverse where one exists. The Euclidean algorithm also has other applications in <a href="Error-correcting_code" class="mw-redirect" title="Error-correcting code">error-correcting codes</a>; for example, it can be used as an alternative to the <a href="Berlekamp%E2%80%93Massey_algorithm" title="Berlekamp–Massey algorithm">Berlekamp–Massey algorithm</a> for decoding <a href="BCH_code" title="BCH code">BCH</a> and <a href="Reed%E2%80%93Solomon_code" class="mw-redirect" title="Reed–Solomon code">Reed–Solomon codes</a>, which are based on Galois fields.<a href="#cite_note-76">[75]</a>

<div class="mw-heading mw-heading3"><h3 id="Chinese_remainder_theorem">Chinese remainder theorem</h3></div>

Euclid's algorithm can also be used to solve multiple linear Diophantine equations.<a href="#cite_note-77">[76]</a> Such equations arise in the <a href="Chinese_remainder_theorem" title="Chinese remainder theorem">Chinese remainder theorem</a>, which describes a novel method to represent an integer x. Instead of representing an integer by its digits, it may be represented by its remainders xi modulo a set of N coprime numbers mi:<a href="#cite_note-78">[77]</a>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}x_{1}&\equiv x{\pmod {m_{1}}}\\x_{2}&\equiv x{\pmod {m_{2}}}\\&\,\,\,\vdots \\x_{N}&\equiv x{\pmod {m_{N}}}\,.\end{aligned}}}</annotation>

</semantics>

</math><img src="./31b5396502c5c41d731d975448aa9db9805d503f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.171ex; width:22.651ex; height:13.509ex;" alt="{\displaystyle {\begin{aligned}x_{1}&\equiv x{\pmod {m_{1}}}\\x_{2}&\equiv x{\pmod {m_{2}}}\\&\,\,\,\vdots \\x_{N}&\equiv x{\pmod {m_{N}}}\,.\end{aligned}}}" loading="lazy"></dd></dl>

The goal is to determine x from its N remainders xi. The solution is to combine the multiple equations into a single linear Diophantine equation with a much larger modulus M that is the product of all the individual moduli mi, and define Mi as

<msub>

</mrow>

</msub>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M_{i}={\frac {M}{m_{i}}}.}</annotation>

</semantics>

</math><img src="./1f3b49175a6f76039f5f0af2949b0685dc124285.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:10.475ex; height:5.509ex;" alt="{\displaystyle M_{i}={\frac {M}{m_{i}}}.}" loading="lazy"></dd></dl>

Thus, each Mi is the product of all the moduli except mi. The solution depends on finding N new numbers hi such that

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M_{i}h_{i}\equiv 1{\pmod {m_{i}}}\,.}</annotation>

</semantics>

</math><img src="./ed2433873b4e6d1c11fc1d5a42d3e0f1720a2e0f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.011ex; height:2.843ex;" alt="{\displaystyle M_{i}h_{i}\equiv 1{\pmod {m_{i}}}\,.}" loading="lazy"></dd></dl>

With these numbers hi, any integer x can be reconstructed from its remainders xi by the equation

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\equiv (x_{1}M_{1}h_{1}+x_{2}M_{2}h_{2}+\cdots +x_{N}M_{N}h_{N}){\pmod {M}}\,.}</annotation>

</semantics>

</math><img src="./8fed369909ea8053d7168a70800c32bcc5e21b24.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:56.81ex; height:2.843ex;" alt="{\displaystyle x\equiv (x_{1}M_{1}h_{1}+x_{2}M_{2}h_{2}+\cdots +x_{N}M_{N}h_{N}){\pmod {M}}\,.}" loading="lazy"></dd></dl>

Since these numbers hi are the multiplicative inverses of the Mi, they may be found using Euclid's algorithm as described in the previous subsection.

<div class="mw-heading mw-heading3"><h3 id="Stern–Brocot_tree">Stern–Brocot tree</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Stern%E2%80%93Brocot_tree" title="Stern–Brocot tree">Stern–Brocot tree</a></div>

The Euclidean algorithm can be used to arrange the set of all positive <a href="Rational_number" title="Rational number">rational numbers</a> into an infinite <a href="Binary_search_tree" title="Binary search tree">binary search tree</a>, called the <a href="Stern%E2%80%93Brocot_tree" title="Stern–Brocot tree">Stern–Brocot tree</a>.

The number 1 (expressed as a fraction 1/1) is placed at the root of the tree, and the location of any other number a/b can be found by computing gcd(a,b) using the original form of the Euclidean algorithm, in which each step replaces the larger of the two given numbers by its difference with the smaller number (not its remainder), stopping when two equal numbers are reached. A step of the Euclidean algorithm that replaces the first of the two numbers corresponds to a step in the tree from a node to its right child, and a step that replaces the second of the two numbers corresponds to a step in the tree from a node to its left child. The sequence of steps constructed in this way does not depend on whether a/b is given in lowest terms, and forms a path from the root to a node containing the number a/b.<a href="#cite_note-79">[78]</a> This fact can be used to prove that each positive rational number appears exactly once in this tree.

For example, 3/4 can be found by starting at the root, going to the left once, then to the right twice:

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}&\gcd(3,4)&\leftarrow \\={}&\gcd(3,1)&\rightarrow \\={}&\gcd(2,1)&\rightarrow \\={}&\gcd(1,1).\end{aligned}}}</annotation>

</semantics>

</math><img src="./3d0bf20425d35b1e9a42b85e40630f5c1263661f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.671ex; width:19.863ex; height:12.509ex;" alt="{\displaystyle {\begin{aligned}&\gcd(3,4)&\leftarrow \\={}&\gcd(3,1)&\rightarrow \\={}&\gcd(2,1)&\rightarrow \\={}&\gcd(1,1).\end{aligned}}}" loading="lazy"></dd></dl>

The Euclidean algorithm has almost the same relationship to another binary tree on the rational numbers called the <a href="Calkin%E2%80%93Wilf_tree" title="Calkin–Wilf tree">Calkin–Wilf tree</a>. The difference is that the path is reversed: instead of producing a path from the root of the tree to a target, it produces a path from the target to the root.

<div class="mw-heading mw-heading3"><h3 id="Continued_fractions">Continued fractions</h3></div>

The Euclidean algorithm has a close relationship with <a href="Continued_fraction" title="Continued fraction">continued fractions</a>.<a href="#cite_note-Vinogradov_1954-80">[79]</a> The sequence of equations can be written in the form

<mtr>

<mtd>

<mfrac>

</mfrac>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<mfrac>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mfrac>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<mfrac>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<mfrac>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<mfrac>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<mfrac>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\frac {a}{b}}&=q_{0}+{\frac {r_{0}}{b}}\\{\frac {b}{r_{0}}}&=q_{1}+{\frac {r_{1}}{r_{0}}}\\{\frac {r_{0}}{r_{1}}}&=q_{2}+{\frac {r_{2}}{r_{1}}}\\&\,\,\,\vdots \\{\frac {r_{k-2}}{r_{k-1}}}&=q_{k}+{\frac {r_{k}}{r_{k-1}}}\\&\,\,\,\vdots \\{\frac {r_{N-2}}{r_{N-1}}}&=q_{N}\,.\end{aligned}}}</annotation>

</semantics>

</math><img src="./b55cba911954b8e8434bd23c6e56826a4f935e29.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -17.005ex; width:19.567ex; height:35.176ex;" alt="{\displaystyle {\begin{aligned}{\frac {a}{b}}&=q_{0}+{\frac {r_{0}}{b}}\\{\frac {b}{r_{0}}}&=q_{1}+{\frac {r_{1}}{r_{0}}}\\{\frac {r_{0}}{r_{1}}}&=q_{2}+{\frac {r_{2}}{r_{1}}}\\&\,\,\,\vdots \\{\frac {r_{k-2}}{r_{k-1}}}&=q_{k}+{\frac {r_{k}}{r_{k-1}}}\\&\,\,\,\vdots \\{\frac {r_{N-2}}{r_{N-1}}}&=q_{N}\,.\end{aligned}}}" loading="lazy"></dd></dl>

The last term on the right-hand side always equals the inverse of the left-hand side of the next equation. Thus, the first two equations may be combined to form

<mfrac>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mpadded>

</mrow>

</mstyle>

</mrow>

<mrow>

</mpadded>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mpadded>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<mrow>

</mpadded>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {r_{1}}{r_{0}}}}}\,.}</annotation>

</semantics>

</math><img src="./0ec09639bf1927ae58b0e48225fafb08b46bec3d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.671ex; width:19.837ex; height:10.843ex;" alt="{\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {r_{1}}{r_{0}}}}}\,.}" loading="lazy"></dd></dl>

The third equation may be used to substitute the denominator term r1/r0, yielding

<mfrac>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mpadded>

</mrow>

</mstyle>

</mrow>

<mrow>

</mpadded>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mpadded>

</mrow>

</mstyle>

</mrow>

<mrow>

</mpadded>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mpadded>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<mrow>

</mpadded>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {1}{q_{2}+{\cfrac {r_{2}}{r_{1}}}}}}}\,.}</annotation>

</semantics>

</math><img src="./fc9747d183fabc6a43a44b7dbc81df348d595e26.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -10.171ex; width:25.605ex; height:14.343ex;" alt="{\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {1}{q_{2}+{\cfrac {r_{2}}{r_{1}}}}}}}\,.}" loading="lazy"></dd></dl>

The final ratio of remainders rk/rk−1 can always be replaced using the next equation in the series, up to the final equation. The result is a continued fraction

<mfrac>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mpadded>

</mrow>

</mstyle>

</mrow>

<mrow>

</mpadded>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mpadded>

</mrow>

</mstyle>

</mrow>

<mrow>

</mpadded>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mpadded>

</mrow>

</mstyle>

</mrow>

<mrow>

</mpadded>

<mfrac>

<mrow>

</mpadded>

</mrow>

</mstyle>

</mrow>

<mrow>

</mpadded>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {1}{q_{2}+{\cfrac {1}{\ddots +{\cfrac {1}{q_{N}}}}}}}}}=[q_{0};q_{1},q_{2},\ldots ,q_{N}]\,.}</annotation>

</semantics>

</math><img src="./bfd6202ce1dc46510c7894abba456c3b899c58bf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -13.838ex; width:53.526ex; height:18.009ex;" alt="{\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {1}{q_{2}+{\cfrac {1}{\ddots +{\cfrac {1}{q_{N}}}}}}}}}=[q_{0};q_{1},q_{2},\ldots ,q_{N}]\,.}" loading="lazy"></dd></dl>

In the worked example <a href="#Worked_example">above</a>, the gcd(1071, 462) was calculated, and the quotients qk were 2, 3 and 7, respectively. Therefore, the fraction 1071/462 may be written

<mfrac>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mpadded>

</mrow>

</mstyle>

</mrow>

<mrow>

</mpadded>

<mfrac>

<mrow>

</mpadded>

</mrow>

</mstyle>

</mrow>

<mrow>

</mpadded>

</mrow>

</mstyle>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {1071}{462}}=2+{\cfrac {1}{3+{\cfrac {1}{7}}}}=[2;3,7]}</annotation>

</semantics>

</math><img src="./41bb1b741861a853bc9f7bcbcd91315b07ffdac0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.671ex; width:29.372ex; height:10.843ex;" alt="{\displaystyle {\frac {1071}{462}}=2+{\cfrac {1}{3+{\cfrac {1}{7}}}}=[2;3,7]}" loading="lazy"></dd></dl>

as can be confirmed by calculation.

<div class="mw-heading mw-heading3"><h3 id="Factorization_algorithms">Factorization algorithms</h3></div>

Calculating a greatest common divisor is an essential step in several <a href="Integer_factorization" title="Integer factorization">integer factorization</a> algorithms,<a href="#cite_note-81">[80]</a> such as <a href="Pollard's_rho_algorithm" title="Pollard's rho algorithm">Pollard's rho algorithm</a>,<a href="#cite_note-82">[81]</a> <a href="Shor's_algorithm" title="Shor's algorithm">Shor's algorithm</a>,<a href="#cite_note-83">[82]</a> <a href="Dixon's_factorization_method" title="Dixon's factorization method">Dixon's factorization method</a><a href="#cite_note-84">[83]</a> and the <a href="Lenstra_elliptic_curve_factorization" class="mw-redirect" title="Lenstra elliptic curve factorization">Lenstra elliptic curve factorization</a>.<a href="#cite_note-85">[84]</a> The Euclidean algorithm may be used to find this GCD efficiently. <a href="Continued_fraction_factorization" title="Continued fraction factorization">Continued fraction factorization</a> uses continued fractions, which are determined using Euclid's algorithm.<a href="#cite_note-86">[85]</a>

<div class="mw-heading mw-heading2"><h2 id="Algorithmic_efficiency">Algorithmic efficiency</h2></div>

The computational efficiency of Euclid's algorithm has been studied thoroughly.<a href="#cite_note-87">[86]</a> This efficiency can be described by the number of division steps the algorithm requires, multiplied by the computational expense of each step. The first known analysis of Euclid's algorithm is due to <a href="Antoine_Andr%C3%A9_Louis_Reynaud" title="Antoine André Louis Reynaud">A. A. L. Reynaud</a> in 1811,<a href="#cite_note-88">[87]</a> who showed that the number of division steps on input (u, v) is bounded by v; later he improved this to v/2 + 2. Later, in 1841, <a href="Pierre_Joseph_%C3%89tienne_Finck" title="Pierre Joseph Étienne Finck">P. J. E. Finck</a> showed<a href="#cite_note-89">[88]</a> that the number of division steps is at most 2 log2 v + 1, and hence Euclid's algorithm runs in time polynomial in the size of the input.<a href="#cite_note-FOOTNOTEShallit1994-90">[89]</a> <a href="%C3%89mile_L%C3%A9ger" title="Émile Léger">Émile Léger</a>, in 1837, studied the worst case, which is when the inputs are consecutive <a href="Fibonacci_numbers" class="mw-redirect" title="Fibonacci numbers">Fibonacci numbers</a>.<a href="#cite_note-FOOTNOTEShallit1994-90">[89]</a> Finck's analysis was refined by <a href="Gabriel_Lam%C3%A9" title="Gabriel Lamé">Gabriel Lamé</a> in 1844,<a href="#cite_note-91">[90]</a> who showed that the number of steps required for completion is never more than five times the number h of base-10 digits of the smaller number b.<a href="#cite_note-92">[91]</a><a href="#cite_note-93">[92]</a>

In the <a href="Uniform_cost_model" class="mw-redirect" title="Uniform cost model">uniform cost model</a> (suitable for analyzing the complexity of gcd calculation on numbers that fit into a single machine word), each step of the algorithm takes <a href="Constant_time" class="mw-redirect" title="Constant time">constant time</a>, and Lamé's analysis implies that the total running time is also O(h). However, in a model of computation suitable for computation with larger numbers, the computational expense of a single remainder computation in the algorithm can be as large as O(h2).<a href="#cite_note-Knuth-257-261-94">[93]</a> In this case the total time for all of the steps of the algorithm can be analyzed using a <a href="Telescoping_series" title="Telescoping series">telescoping series</a>, showing that it is also O(h2). Modern algorithmic techniques based on the <a href="Sch%C3%B6nhage%E2%80%93Strassen_algorithm" title="Schönhage–Strassen algorithm">Schönhage–Strassen algorithm</a> for fast integer multiplication can be used to speed this up, leading to <a href="Quasilinear_time" class="mw-redirect" title="Quasilinear time">quasilinear algorithms</a> for the GCD.<a href="#cite_note-Crandall_2001-95">[94]</a><a href="#cite_note-Moller08-96">[95]</a>

<div class="mw-heading mw-heading3"><h3 id="Number_of_steps">Number of steps</h3></div>

The number of steps to calculate the GCD of two natural numbers, a and b, may be denoted by T(a, b).<a href="#cite_note-Knuth,_p._344-97">[96]</a> If g is the GCD of a and b, then a = mg and b = ng for two coprime numbers m and n. Then

as may be seen by dividing all the steps in the Euclidean algorithm by g.<a href="#cite_note-98">[97]</a> By the same argument, the number of steps remains the same if a and b are multiplied by a common factor w: T(a, b) = T(wa, wb). Therefore, the number of steps T may vary dramatically between neighboring pairs of numbers, such as T(a, b) and T(a, b + 1), depending on the size of the two GCDs.

The recursive nature of the Euclidean algorithm gives another equation

where T(x, 0) = 0 by assumption.<a href="#cite_note-Knuth,_p._344-97">[96]</a>

<div class="mw-heading mw-heading4"><h4 id="Worst-case">Worst-case</h4></div>

If the Euclidean algorithm requires N steps for a pair of natural numbers a > b > 0, the smallest values of a and b for which this is true are the <a href="Fibonacci_number" class="mw-redirect" title="Fibonacci number">Fibonacci numbers</a> FN+2 and FN+1, respectively.<a href="#cite_note-Knuth,_p._343-99">[98]</a> More precisely, if the Euclidean algorithm requires N steps for the pair a > b, then one has a ≥ FN+2 and b ≥ FN+1. This can be shown by <a href="Mathematical_induction" title="Mathematical induction">induction</a>.<a href="#cite_note-100">[99]</a> If N = 1, b divides a with no remainder; the smallest natural numbers for which this is true is b = 1 and a = 2, which are F2 and F3, respectively. Now assume that the result holds for all values of N up to M − 1. The first step of the M-step algorithm is a = q0b + r0, and the Euclidean algorithm requires M − 1 steps for the pair b > r0. By induction hypothesis, one has b ≥ FM+1 and r0 ≥ FM. Therefore, a = q0b + r0 ≥ b + r0 ≥ FM+1 + FM = FM+2,

which is the desired inequality.

This proof, published by <a href="Gabriel_Lam%C3%A9" title="Gabriel Lamé">Gabriel Lamé</a> in 1844, represents the beginning of <a href="Computational_complexity_theory" title="Computational complexity theory">computational complexity theory</a>,<a href="#cite_note-101">[100]</a> and also the first practical application of the Fibonacci numbers.<a href="#cite_note-Knuth,_p._343-99">[98]</a>

This result suffices to show that the number of steps in Euclid's algorithm can never be more than five times the number of its digits (base 10).<a href="#cite_note-102">[101]</a> For if the algorithm requires N steps, then b is greater than or equal to FN+1 which in turn is greater than or equal to φN−1, where φ is the <a href="Golden_ratio" title="Golden ratio">golden ratio</a>. Since b ≥ φN−1, then N − 1 ≤ logφb. Since log10φ > 1/5, (N − 1)/5 < log10φ logφb = log10b. Thus, N ≤ 5 log10b. Thus, the Euclidean algorithm always needs less than <a href="Big_O_notation" title="Big O notation">O(h)</a> divisions, where h is the number of digits in the smaller number b.

<div class="mw-heading mw-heading4"><h4 id="Average">Average</h4></div>

The average number of steps taken by the Euclidean algorithm has been defined in three different ways. The first definition is the average time T(a) required to calculate the GCD of a given number a and a smaller natural number b chosen with equal probability from the integers 0 to a − 1<a href="#cite_note-Knuth,_p._344-97">[96]</a>

<mfrac>

</mfrac>

</mrow>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T(a)={\frac {1}{a}}\sum _{0\leq b<a}T(a,b).}</annotation>

</semantics>

</math><img src="./eeb0e84ea4b825926a619f0738568e20d52f9a25.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:22.922ex; height:6.676ex;" alt="{\displaystyle T(a)={\frac {1}{a}}\sum _{0\leq b<a}T(a,b).}" loading="lazy"></dd></dl>

However, since T(a, b) fluctuates dramatically with the GCD of the two numbers, the averaged function T(a) is likewise "noisy".<a href="#cite_note-103">[102]</a>

To reduce this noise, a second average τ(a) is taken over all numbers coprime with a

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mstyle>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \tau (a)={\frac {1}{\varphi (a)}}\sum _{\begin{smallmatrix}0\leq b<a\\\gcd(a,b)=1\end{smallmatrix}}T(a,b).}</annotation>

</semantics>

</math><img src="./1a59110d2108bbad28857056ec51eb6c1c580524.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.338ex; width:29.492ex; height:8.676ex;" alt="{\displaystyle \tau (a)={\frac {1}{\varphi (a)}}\sum _{\begin{smallmatrix}0\leq b<a\\\gcd(a,b)=1\end{smallmatrix}}T(a,b).}" loading="lazy"></dd></dl>

There are φ(a) coprime integers less than a, where φ is <a href="Euler's_totient_function" title="Euler's totient function">Euler's totient function</a>. This tau average grows smoothly with a<a href="#cite_note-104">[103]</a><a href="#cite_note-105">[104]</a>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \tau (a)={\frac {12}{\pi ^{2}}}\ln 2\ln a+C+O(a^{-1/6-\varepsilon })}</annotation>

</semantics>

</math><img src="./977ed1b32dc273f67a46fb6e410666e8acf0289b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:36.664ex; height:5.509ex;" alt="{\displaystyle \tau (a)={\frac {12}{\pi ^{2}}}\ln 2\ln a+C+O(a^{-1/6-\varepsilon })}" loading="lazy"></dd></dl>

with the residual error being of order a−(1/6)+ε, where ε is <a href="Infinitesimal" title="Infinitesimal">infinitesimal</a>. The constant C in this formula is called <a href="Porter's_constant" title="Porter's constant">Porter's constant</a><a href="#cite_note-106">[105]</a> and equals

<mfrac>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

<mrow>

<mrow>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

<msup>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C=-{\frac {1}{2}}+{\frac {6\ln 2}{\pi ^{2}}}\left(4\gamma -{\frac {24}{\pi ^{2}}}\zeta '(2)+3\ln 2-2\right)\approx 1.467}</annotation>

</semantics>

</math><img src="./574e559226f674eed4201564e269c7ad9b8b6555.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:54.736ex; height:6.176ex;" alt="{\displaystyle C=-{\frac {1}{2}}+{\frac {6\ln 2}{\pi ^{2}}}\left(4\gamma -{\frac {24}{\pi ^{2}}}\zeta '(2)+3\ln 2-2\right)\approx 1.467}" loading="lazy"></dd></dl>

where γ is the <a href="Euler%E2%80%93Mascheroni_constant" class="mw-redirect" title="Euler–Mascheroni constant">Euler–Mascheroni constant</a> and ζ′ is the <a href="Derivative" title="Derivative">derivative</a> of the <a href="Riemann_zeta_function" title="Riemann zeta function">Riemann zeta function</a>.<a href="#cite_note-107">[106]</a><a href="#cite_note-108">[107]</a> The leading coefficient (12/π2) ln 2 was determined by two independent methods.<a href="#cite_note-109">[108]</a><a href="#cite_note-110">[109]</a>

Since the first average can be calculated from the tau average by summing over the divisors d of a<a href="#cite_note-111">[110]</a>

<mfrac>

</mfrac>

</mrow>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T(a)={\frac {1}{a}}\sum _{d\mid a}\varphi (d)\tau (d)}</annotation>

</semantics>

</math><img src="./b6fdf23824b83cb21d9f4eb0e5f6811c12fe6561.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:22.741ex; height:6.843ex;" alt="{\displaystyle T(a)={\frac {1}{a}}\sum _{d\mid a}\varphi (d)\tau (d)}" loading="lazy"></dd></dl>

it can be approximated by the formula<a href="#cite_note-Norton_1990-112">[111]</a>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mrow>

</mrow>

</mrow>

</munder>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T(a)\approx C+{\frac {12}{\pi ^{2}}}\ln 2\,{\biggl (}{\ln a}-\sum _{d\mid a}{\frac {\Lambda (d)}{d}}{\biggr )}}</annotation>

</semantics>

</math><img src="./57dcbb8dcface89d1bdfe3b1f46581380e8df13e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:38.903ex; height:7.343ex;" alt="{\displaystyle T(a)\approx C+{\frac {12}{\pi ^{2}}}\ln 2\,{\biggl (}{\ln a}-\sum _{d\mid a}{\frac {\Lambda (d)}{d}}{\biggr )}}" loading="lazy"></dd></dl>

where Λ(d) is the <a href="Von_Mangoldt_function" title="Von Mangoldt function">Mangoldt function</a>.<a href="#cite_note-113">[112]</a>

A third average Y(n) is defined as the mean number of steps required when both a and b are chosen randomly (with uniform distribution) from 1 to n<a href="#cite_note-Norton_1990-112">[111]</a>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</munderover>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y(n)={\frac {1}{n^{2}}}\sum _{a=1}^{n}\sum _{b=1}^{n}T(a,b)={\frac {1}{n}}\sum _{a=1}^{n}T(a).}</annotation>

</semantics>

</math><img src="./b1daf73a2c348ca3894312d10cbad0b7cc6c015c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:40.72ex; height:6.843ex;" alt="{\displaystyle Y(n)={\frac {1}{n^{2}}}\sum _{a=1}^{n}\sum _{b=1}^{n}T(a,b)={\frac {1}{n}}\sum _{a=1}^{n}T(a).}" loading="lazy"></dd></dl>

Substituting the approximate formula for T(a) into this equation yields an estimate for Y(n)<a href="#cite_note-114">[113]</a>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y(n)\approx {\frac {12}{\pi ^{2}}}\ln 2\ln n+0.06.}</annotation>

</semantics>

</math><img src="./90c528cb5f169ef20bc53312c80d3e786634243c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:26.906ex; height:5.509ex;" alt="{\displaystyle Y(n)\approx {\frac {12}{\pi ^{2}}}\ln 2\ln n+0.06.}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Computational_expense_per_step">Computational expense per step</h3></div>

In each step k of the Euclidean algorithm, the quotient qk and remainder rk are computed for a given pair of integers rk−2 and rk−1

The computational expense per step is associated chiefly with finding qk, since the remainder rk can be calculated quickly from rk−2, rk−1, and qk

The computational expense of dividing h-bit numbers scales as O(h(ℓ + 1)), where ℓ is the length of the quotient.<a href="#cite_note-Knuth-257-261-94">[93]</a>

For comparison, Euclid's original subtraction-based algorithm can be much slower. A single integer division is equivalent to the quotient q number of subtractions. If the ratio of a and b is very large, the quotient is large and many subtractions will be required. On the other hand, it has been shown that the quotients are very likely to be small integers. The probability of a given quotient q is approximately ln |u/(u − 1)| where u = (q + 1)2.<a href="#cite_note-115">[114]</a> For illustration, the probability of a quotient of 1, 2, 3, or 4 is roughly 41.5%, 17.0%, 9.3%, and 5.9%, respectively. Since the operation of subtraction is faster than division, particularly for large numbers,<a href="#cite_note-116">[115]</a> the subtraction-based Euclid's algorithm is competitive with the division-based version.<a href="#cite_note-117">[116]</a> This is exploited in the <a href="Binary_GCD_algorithm" title="Binary GCD algorithm">binary version</a> of Euclid's algorithm.<a href="#cite_note-118">[117]</a>

Combining the estimated number of steps with the estimated computational expense per step shows that the Euclid's algorithm grows quadratically (h2) with the average number of digits h in the initial two numbers a and b. Let h0, h1, ..., hN−1 represent the number of digits in the successive remainders r0, r1, ..., rN−1. Since the number of steps N grows linearly with h, the running time is bounded by

</mrow>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O{\Big (}\sum _{i<N}h_{i}(h_{i}-h_{i+1}+2){\Big )}\subseteq O{\Big (}h\sum _{i<N}(h_{i}-h_{i+1}+2){\Big )}\subseteq O(h(h_{0}+2N))\subseteq O(h^{2}).}</annotation>

</semantics>

</math><img src="./f42bdfff58a9962834d6a5650c867ddcb7d46216.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:81.616ex; height:6.176ex;" alt="{\displaystyle O{\Big (}\sum _{i<N}h_{i}(h_{i}-h_{i+1}+2){\Big )}\subseteq O{\Big (}h\sum _{i<N}(h_{i}-h_{i+1}+2){\Big )}\subseteq O(h(h_{0}+2N))\subseteq O(h^{2}).}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Alternative_methods">Alternative methods</h3></div>

Euclid's algorithm is widely used in practice, especially for small numbers, due to its simplicity.<a href="#cite_note-119">[118]</a> For comparison, the efficiency of alternatives to Euclid's algorithm may be determined.

One inefficient approach to finding the GCD of two natural numbers a and b is to calculate all their common divisors; the GCD is then the largest common divisor. The common divisors can be found by dividing both numbers by successive integers from 2 to the smaller number b. The number of steps of this approach grows linearly with b, or exponentially in the number of digits. Another inefficient approach is to find the prime factors of one or both numbers. As noted <a href="#Greatest_common_divisor">above</a>, the GCD equals the product of the prime factors shared by the two numbers a and b.<a href="#cite_note-Schroeder_21-9">[8]</a> Present methods for <a href="Integer_factorization" title="Integer factorization">prime factorization</a> are also inefficient; many modern cryptography systems even rely on that inefficiency.<a href="#cite_note-Schroeder_216-12">[11]</a>

The <a href="Binary_GCD_algorithm" title="Binary GCD algorithm">binary GCD algorithm</a> is an efficient alternative that substitutes division with faster operations by exploiting the <a href="Binary_numeral_system" class="mw-redirect" title="Binary numeral system">binary</a> representation used by computers.<a href="#cite_note-120">[119]</a><a href="#cite_note-121">[120]</a> However, this alternative also scales like <a href="Big-O_notation" class="mw-redirect" title="Big-O notation">O(h²)</a>. It is generally faster than the Euclidean algorithm on real computers, even though it scales in the same way.<a href="#cite_note-Crandall_2001-95">[94]</a> Additional efficiency can be gleaned by examining only the leading digits of the two numbers a and b.<a href="#cite_note-122">[121]</a><a href="#cite_note-123">[122]</a> The binary algorithm can be extended to other bases (k-ary algorithms),<a href="#cite_note-124">[123]</a> with up to fivefold increases in speed.<a href="#cite_note-125">[124]</a> <a href="Lehmer's_GCD_algorithm" title="Lehmer's GCD algorithm">Lehmer's GCD algorithm</a> uses the same general principle as the binary algorithm to speed up GCD computations in arbitrary bases.

A recursive approach for very large integers (with more than 25,000 digits) leads to <a href="Quasilinear_time" class="mw-redirect" title="Quasilinear time">quasilinear</a> integer GCD algorithms,<a href="#cite_note-126">[125]</a> such as those of Schönhage,<a href="#cite_note-127">[126]</a><a href="#cite_note-128">[127]</a> and Stehlé and Zimmermann.<a href="#cite_note-129">[128]</a> These algorithms exploit the 2×2 matrix form of the Euclidean algorithm given <a href="#Matrix_method">above</a>. These quasilinear methods generally scale as O(h log h2 log log h).<a href="#cite_note-Crandall_2001-95">[94]</a><a href="#cite_note-Moller08-96">[95]</a>

<div class="mw-heading mw-heading2"><h2 id="Generalizations">Generalizations</h2></div>

Although the Euclidean algorithm is used to find the greatest common divisor of two natural numbers (positive integers), it may be generalized to the real numbers, and to other mathematical objects, such as <a href="Polynomial" title="Polynomial">polynomials</a>,<a href="#cite_note-Lang_1984-130">[129]</a> <a href="Quadratic_integer" title="Quadratic integer">quadratic integers</a><a href="#cite_note-weinberger-131">[130]</a> and <a href="Hurwitz_quaternion" title="Hurwitz quaternion">Hurwitz quaternions</a>.<a href="#cite_note-stillwell151-152-132">[131]</a> In the latter cases, the Euclidean algorithm is used to demonstrate the crucial property of unique factorization, i.e., that such numbers can be factored uniquely into <a href="Irreducible_element" title="Irreducible element">irreducible elements</a>, the counterparts of prime numbers. Unique factorization is essential to many proofs of number theory.

<div class="mw-heading mw-heading3"><h3 id="Rational_and_real_numbers">Rational and real numbers</h3></div>

Euclid's algorithm can be applied to <a href="Real_number" title="Real number">real numbers</a>, as described by Euclid in Book 10 of his <a href="Euclid's_Elements" title="Euclid's Elements">Elements</a>. The goal of the algorithm is to identify a real number g such that two given real numbers, a and b, are integer multiples of it: a = mg and b = ng, where m and n are <a href="Integer" title="Integer">integers</a>.<a href="#cite_note-Weil_1983-29">[28]</a> This identification is equivalent to finding an <a href="Integer_relation_algorithm" title="Integer relation algorithm">integer relation</a> among the real numbers a and b; that is, it determines integers s and t such that sa + tb = 0. If such an equation is possible, a and b are called commensurable lengths, otherwise they are <a href="Commensurability_(mathematics)" title="Commensurability (mathematics)">incommensurable lengths</a>.<a href="#cite_note-133">[132]</a><a href="#cite_note-134">[133]</a>

The real-number Euclidean algorithm differs from its integer counterpart in two respects. First, the remainders rk are real numbers, although the quotients qk are integers as before. Second, the algorithm is not guaranteed to end in a finite number N of steps. If it does, the fraction a/b is a rational number, i.e., the ratio of two integers

<mfrac>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {a}{b}}={\frac {mg}{ng}}={\frac {m}{n}},}</annotation>

</semantics>

</math><img src="./ebe70bc1e1fa440faa4c9029ff65f0947ae83e64.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:15.779ex; height:5.343ex;" alt="{\displaystyle {\frac {a}{b}}={\frac {mg}{ng}}={\frac {m}{n}},}" loading="lazy"></dd></dl>

and can be written as a finite continued fraction [q0; q1, q2, ..., qN]. If the algorithm does not stop, the fraction a/b is an <a href="Irrational_number" title="Irrational number">irrational number</a> and can be described by an infinite continued fraction [q0; q1, q2, …].<a href="#cite_note-135">[134]</a> Examples of infinite continued fractions are the <a href="Golden_ratio" title="Golden ratio">golden ratio</a> φ = [1; 1, 1, ...] and the <a href="Square_root_of_2" title="Square root of 2">square root of two</a>, √2 = [1; 2, 2, ...].<a href="#cite_note-136">[135]</a> When applied to two arbitrary real numbers, the algorithm is unlikely to stop, since <a href="Almost_all" title="Almost all">almost all</a> ratios a/b of two real numbers are irrational.<a href="#cite_note-137">[136]</a>

An infinite continued fraction may be truncated at a step k [q0; q1, q2, ..., qk] to yield an approximation to a/b that improves as k is increased. The approximation is described by <a href="Convergent_(continued_fraction)" class="mw-redirect" title="Convergent (continued fraction)">convergents</a> mk/nk; the numerator and denominators are coprime and obey the <a href="Recurrence_relation" title="Recurrence relation">recurrence relation</a>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}m_{k}&=q_{k}m_{k-1}+m_{k-2}\\n_{k}&=q_{k}n_{k-1}+n_{k-2},\end{aligned}}}</annotation>

</semantics>

</math><img src="./c2246f4f03913cc9726e4924ecc9776513ec7136.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.111ex; margin-bottom: -0.227ex; width:22.405ex; height:5.843ex;" alt="{\displaystyle {\begin{aligned}m_{k}&=q_{k}m_{k-1}+m_{k-2}\\n_{k}&=q_{k}n_{k-1}+n_{k-2},\end{aligned}}}" loading="lazy"></dd></dl>

where m−1 = n−2 = 1 and m−2 = n−1 = 0 are the initial values of the recursion. The convergent mk/nk is the best <a href="Rational_number" title="Rational number">rational number</a> approximation to a/b with denominator nk:<a href="#cite_note-138">[137]</a>

<mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

<mfrac>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mrow>

<mfrac>

</mrow>

</mrow>

</msubsup>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left|{\frac {a}{b}}-{\frac {m_{k}}{n_{k}}}\right|<{\frac {1}{n_{k}^{2}}}.}</annotation>

</semantics>

</math><img src="./f2d2e3ea02f68f2bfe4a20aabff8d92dace95747.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:17.23ex; height:6.343ex;" alt="{\displaystyle \left|{\frac {a}{b}}-{\frac {m_{k}}{n_{k}}}\right|<{\frac {1}{n_{k}^{2}}}.}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Polynomials">Polynomials</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Polynomial_greatest_common_divisor" title="Polynomial greatest common divisor">Polynomial greatest common divisor</a></div>

Polynomials in a single variable x can be added, multiplied and factored into <a href="Irreducible_polynomial" title="Irreducible polynomial">irreducible polynomials</a>, which are the analogs of the prime numbers for integers. The greatest common divisor polynomial g(x) of two polynomials a(x) and b(x) is defined as the product of their shared irreducible polynomials, which can be identified using the Euclidean algorithm.<a href="#cite_note-Lang_1984-130">[129]</a> The basic procedure is similar to that for integers. At each step k, a quotient polynomial qk(x) and a remainder polynomial rk(x) are identified to satisfy the recursive equation

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{k-2}(x)=q_{k}(x)r_{k-1}(x)+r_{k}(x),}</annotation>

</semantics>

</math><img src="./9a124a8ba0c2bafb28022d39fda1b09864b696b1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.881ex; height:2.843ex;" alt="{\displaystyle r_{k-2}(x)=q_{k}(x)r_{k-1}(x)+r_{k}(x),}" loading="lazy"></dd></dl>

where r−2(x) = a(x) and r−1(x) = b(x). Each quotient polynomial is chosen such that each remainder is either zero or has a degree that is smaller than the degree of its predecessor: deg[rk(x)] < deg[rk−1(x)]. Since the degree is a nonnegative integer, and since it decreases with every step, the Euclidean algorithm concludes in a finite number of steps. The last nonzero remainder is the greatest common divisor of the original two polynomials, a(x) and b(x).<a href="#cite_note-139">[138]</a>

For example, consider the following two quartic polynomials, which each factor into two quadratic polynomials

<mtr>

<mtd>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}a(x)&=x^{4}-4x^{3}+4x^{2}-3x+14=(x^{2}-5x+7)(x^{2}+x+2)\qquad {\text{and}}\\b(x)&=x^{4}+8x^{3}+12x^{2}+17x+6=(x^{2}+7x+3)(x^{2}+x+2).\end{aligned}}}</annotation>

</semantics>

</math><img src="./5017293fab5cb800af9c776f0b133f45674850dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:71.26ex; height:6.509ex;" alt="{\displaystyle {\begin{aligned}a(x)&=x^{4}-4x^{3}+4x^{2}-3x+14=(x^{2}-5x+7)(x^{2}+x+2)\qquad {\text{and}}\\b(x)&=x^{4}+8x^{3}+12x^{2}+17x+6=(x^{2}+7x+3)(x^{2}+x+2).\end{aligned}}}" loading="lazy"></dd></dl>

<a href="Polynomial_long_division" title="Polynomial long division">Dividing</a> a(x) by b(x) yields a remainder r0(x) = x3 + (2/3)x2 + (5/3)x − (2/3). In the next step, b(x) is divided by r0(x) yielding a remainder r1(x) = x2 + x + 2. Finally, dividing r0(x) by r1(x) yields a zero remainder, indicating that r1(x) is the greatest common divisor polynomial of a(x) and b(x), consistent with their factorization.

Many of the applications described above for integers carry over to polynomials.<a href="#cite_note-140">[139]</a> The Euclidean algorithm can be used to solve linear Diophantine equations and Chinese remainder problems for polynomials; continued fractions of polynomials can also be defined.

The polynomial Euclidean algorithm has other applications, such as <a href="Sturm_chain" class="mw-redirect" title="Sturm chain">Sturm chains</a>, a method for counting the <a href="Zero_of_a_function" title="Zero of a function">zeros of a polynomial</a> that lie inside a given <a href="Interval_(mathematics)" title="Interval (mathematics)">real interval</a>.<a href="#cite_note-141">[140]</a> This in turn has applications in several areas, such as the <a href="Routh%E2%80%93Hurwitz_stability_criterion" title="Routh–Hurwitz stability criterion">Routh–Hurwitz stability criterion</a> in <a href="Control_theory" title="Control theory">control theory</a>.<a href="#cite_note-142">[141]</a>

Finally, the coefficients of the polynomials need not be drawn from integers, real numbers or even the complex numbers. For example, the coefficients may be drawn from a general field, such as the finite fields GF(p) described above. The corresponding conclusions about the Euclidean algorithm and its applications hold even for such polynomials.<a href="#cite_note-Lang_1984-130">[129]</a>

<div class="mw-heading mw-heading3"><h3 id="Gaussian_integers">Gaussian integers</h3></div>

The <a href="Gaussian_integer" title="Gaussian integer">Gaussian integers</a> are <a href="Complex_number" title="Complex number">complex numbers</a> of the form α = u + vi, where u and v are ordinary <a href="Integer" title="Integer">integers</a><a href="#cite_note-143">[note 2]</a> and i is the <a href="Imaginary_unit" title="Imaginary unit">square root of negative one</a>.<a href="#cite_note-Stillwell_2003-144">[142]</a> By defining an analog of the Euclidean algorithm, Gaussian integers can be shown to be uniquely factorizable, by the argument <a href="#Bézout's_identity">above</a>.<a href="#cite_note-Gauss_1832-44">[43]</a> This unique factorization is helpful in many applications, such as deriving all <a href="Pythagorean_triple" title="Pythagorean triple">Pythagorean triples</a> or proving <a href="Fermat's_theorem_on_sums_of_two_squares" title="Fermat's theorem on sums of two squares">Fermat's theorem on sums of two squares</a>.<a href="#cite_note-Stillwell_2003-144">[142]</a> In general, the Euclidean algorithm is convenient in such applications, but not essential; for example, the theorems can often be proven by other arguments.

The Euclidean algorithm developed for two Gaussian integers α and β is nearly the same as that for ordinary integers,<a href="#cite_note-hensley-145">[143]</a> but differs in two respects. As before, we set r−2 = α and r−1 = β, and the task at each step k is to identify a quotient qk and a remainder rk such that

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r_{k}=r_{k-2}-q_{k}r_{k-1},}</annotation>

</semantics>

</math><img src="./4d869488f195aa53279b6ed587a3537815c4ed51.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:19.325ex; height:2.343ex;" alt="{\displaystyle r_{k}=r_{k-2}-q_{k}r_{k-1},}" loading="lazy"></dd></dl>

where every remainder is strictly smaller than its predecessor: |rk| < |rk−1|. The first difference is that the quotients and remainders are themselves Gaussian integers, and thus are <a href="Complex_number" title="Complex number">complex numbers</a>. The quotients qk are generally found by rounding the real and complex parts of the exact ratio (such as the complex number α/β) to the nearest integers.<a href="#cite_note-hensley-145">[143]</a> The second difference lies in the necessity of defining how one complex remainder can be "smaller" than another. To do this, a <a href="Norm_(mathematics)" title="Norm (mathematics)">norm function</a> f(u + vi) = u2 + v2 is defined, which converts every Gaussian integer u + vi into an ordinary integer. After each step k of the Euclidean algorithm, the norm of the remainder f(rk) is smaller than the norm of the preceding remainder, f(rk−1). Since the norm is a nonnegative integer and decreases with every step, the Euclidean algorithm for Gaussian integers ends in a finite number of steps.<a href="#cite_note-146">[144]</a> The final nonzero remainder is gcd(α, β), the Gaussian integer of largest norm that divides both α and β; it is unique up to multiplication by a unit, ±1 or ±i.<a href="#cite_note-147">[145]</a>

Many of the other applications of the Euclidean algorithm carry over to Gaussian integers. For example, it can be used to solve linear Diophantine equations and Chinese remainder problems for Gaussian integers;<a href="#cite_note-148">[146]</a> continued fractions of Gaussian integers can also be defined.<a href="#cite_note-hensley-145">[143]</a>

<div class="mw-heading mw-heading3"><h3 id="Euclidean_domains">Euclidean domains</h3></div>

A set of elements under two <a href="Binary_operation" title="Binary operation">binary operations</a>, denoted as addition and multiplication, is called a <a href="Euclidean_domain" title="Euclidean domain">Euclidean domain</a> if it forms a <a href="Commutative_ring" title="Commutative ring">commutative ring</a> R and, roughly speaking, if a generalized Euclidean algorithm can be performed on them.<a href="#cite_note-149">[147]</a><a href="#cite_note-150">[148]</a> The two operations of such a ring need not be the addition and multiplication of ordinary arithmetic; rather, they can be more general, such as the operations of a <a href="Group_(mathematics)" title="Group (mathematics)">mathematical group</a> or <a href="Monoid" title="Monoid">monoid</a>. Nevertheless, these general operations should respect many of the laws governing ordinary arithmetic, such as <a href="Commutative_property" title="Commutative property">commutativity</a>, <a href="Associative_property" title="Associative property">associativity</a> and <a href="Distributive_property" title="Distributive property">distributivity</a>.

The generalized Euclidean algorithm requires a Euclidean function, i.e., a mapping f from R into the set of nonnegative integers such that, for any two nonzero elements a and b in R, there exist q and r in R such that a = qb + r and f(r) < f(b).<a href="#cite_note-151">[149]</a> Examples of such mappings are the absolute value for integers, the degree for <a href="Univariate_polynomial" class="mw-redirect" title="Univariate polynomial">univariate polynomials</a>, and the norm for Gaussian integers <a href="#Gaussian_integers">above</a>.<a href="#cite_note-152">[150]</a><a href="#cite_note-153">[151]</a> The basic principle is that each step of the algorithm reduces f inexorably; hence, if f can be reduced only a finite number of times, the algorithm must stop in a finite number of steps. This principle relies on the <a href="Well-order" title="Well-order">well-ordering</a> property of the non-negative integers, which asserts that every non-empty set of non-negative integers has a smallest member.<a href="#cite_note-sharpe-154">[152]</a>

The <a href="Fundamental_theorem_of_arithmetic" title="Fundamental theorem of arithmetic">fundamental theorem of arithmetic</a> applies to any Euclidean domain: Any number from a Euclidean domain can be factored uniquely into <a href="Irreducible_element" title="Irreducible element">irreducible elements</a>. Any Euclidean domain is a <a href="Unique_factorization_domain" title="Unique factorization domain">unique factorization domain</a> (UFD), although the converse is not true.<a href="#cite_note-sharpe-154">[152]</a> The Euclidean domains and the UFD's are subclasses of the <a href="GCD_domain" title="GCD domain">GCD domains</a>, domains in which a greatest common divisor of two numbers always exists.<a href="#cite_note-155">[153]</a> In other words, a greatest common divisor may exist (for all pairs of elements in a domain), although it may not be possible to find it using a Euclidean algorithm. A Euclidean domain is always a <a href="Principal_ideal_domain" title="Principal ideal domain">principal ideal domain</a> (PID), an <a href="Integral_domain" title="Integral domain">integral domain</a> in which every <a href="Ideal_(ring_theory)" title="Ideal (ring theory)">ideal</a> is a <a href="Principal_ideal" title="Principal ideal">principal ideal</a>.<a href="#cite_note-156">[154]</a> Again, the converse is not true: not every PID is a Euclidean domain.

The unique factorization of Euclidean domains is useful in many applications. For example, the unique factorization of the Gaussian integers is convenient in deriving formulae for all <a href="Pythagorean_triple" title="Pythagorean triple">Pythagorean triples</a> and in proving <a href="Fermat's_theorem_on_sums_of_two_squares" title="Fermat's theorem on sums of two squares">Fermat's theorem on sums of two squares</a>.<a href="#cite_note-Stillwell_2003-144">[142]</a> Unique factorization was also a key element in an attempted proof of <a href="Fermat's_Last_Theorem" title="Fermat's Last Theorem">Fermat's Last Theorem</a> published in 1847 by Gabriel Lamé, the same mathematician who analyzed the efficiency of Euclid's algorithm, based on a suggestion of <a href="Joseph_Liouville" title="Joseph Liouville">Joseph Liouville</a>.<a href="#cite_note-157">[155]</a> Lamé's approach required the unique factorization of numbers of the form x + ωy, where x and y are integers, and ω = e2iπ/n is an nth root of 1, that is, ωn = 1. Although this approach succeeds for some values of n (such as n = 3, the <a href="Eisenstein_integer" title="Eisenstein integer">Eisenstein integers</a>), in general such numbers do not factor uniquely. This failure of unique factorization in some <a href="Cyclotomic_field" title="Cyclotomic field">cyclotomic fields</a> led <a href="Ernst_Kummer" title="Ernst Kummer">Ernst Kummer</a> to the concept of <a href="Ideal_number" title="Ideal number">ideal numbers</a> and, later, <a href="Richard_Dedekind" title="Richard Dedekind">Richard Dedekind</a> to <a href="Ideal_(ring_theory)" title="Ideal (ring theory)">ideals</a>.<a href="#cite_note-158">[156]</a>

<div class="mw-heading mw-heading4"><h4 id="Unique_factorization_of_quadratic_integers">Unique factorization of quadratic integers</h4></div>

The <a href="Quadratic_integer" title="Quadratic integer">quadratic integer</a> rings are helpful to illustrate Euclidean domains. Quadratic integers are generalizations of the Gaussian integers in which the <a href="Imaginary_unit" title="Imaginary unit">imaginary unit</a> i is replaced by a number ω. Thus, they have the form u + vω, where u and v are integers and ω has one of two forms, depending on a parameter D. If D does not equal a multiple of four plus one, then

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \omega ={\sqrt {D}}.}</annotation>

</semantics>

</math><img src="./0a727dc9de031c71ccacf6617ac07a816ed3ba3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.051ex; height:3.009ex;" alt="{\displaystyle \omega ={\sqrt {D}}.}" loading="lazy"></dd></dl>

If, however, D does equal a multiple of four plus one, then

<mfrac>

<mrow>

<msqrt>

</msqrt>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \omega ={\frac {1+{\sqrt {D}}}{2}}.}</annotation>

</semantics>

</math><img src="./cd3f1793eef655097a24765d6b48d950a45302ea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:13.89ex; height:5.843ex;" alt="{\displaystyle \omega ={\frac {1+{\sqrt {D}}}{2}}.}" loading="lazy"></dd></dl>

If the function f corresponds to a <a href="Field_norm" title="Field norm">norm</a> function, such as that used to order the Gaussian integers <a href="#Gaussian_integers">above</a>, then the domain is known as <a href="Norm-Euclidean_field" class="mw-redirect" title="Norm-Euclidean field">norm-Euclidean</a>. The norm-Euclidean rings of quadratic integers are exactly those where D is one of the values −11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, or 73.<a href="#cite_note-159">[157]</a><a href="#cite_note-160">[158]</a> The cases D = −1 and D = −3 yield the <a href="Gaussian_integer" title="Gaussian integer">Gaussian integers</a> and <a href="Eisenstein_integer" title="Eisenstein integer">Eisenstein integers</a>, respectively.

If f is allowed to be any Euclidean function, then the list of possible values of D for which the domain is Euclidean is not yet known.<a href="#cite_note-Clark_1994-161">[159]</a> The first example of a Euclidean domain that was not norm-Euclidean (with D = 69) was published in 1994.<a href="#cite_note-Clark_1994-161">[159]</a> In 1973, Weinberger proved that a quadratic integer ring with D > 0 is Euclidean if, and only if, it is a <a href="Principal_ideal_domain" title="Principal ideal domain">principal ideal domain</a>, provided that the <a href="Generalized_Riemann_hypothesis" title="Generalized Riemann hypothesis">generalized Riemann hypothesis</a> holds.<a href="#cite_note-weinberger-131">[130]</a>

<div class="mw-heading mw-heading3"><h3 id="Noncommutative_rings">Noncommutative rings</h3></div>

The Euclidean algorithm may be applied to some noncommutative rings such as the set of <a href="Hurwitz_quaternion" title="Hurwitz quaternion">Hurwitz quaternions</a>.<a href="#cite_note-stillwell151-152-132">[131]</a><a href="#cite_note-bgv-162">[160]</a> Let α and β represent two elements from such a ring. They have a common right divisor δ if α = ξδ and β = ηδ for some choice of ξ and η in the ring. Similarly, they have a common left divisor if α = dξ and β = dη for some choice of ξ and η in the ring. Since multiplication is not commutative, there are two versions of the Euclidean algorithm, one for right divisors and one for left divisors.<a href="#cite_note-stillwell151-152-132">[131]</a><a href="#cite_note-bgv-162">[160]</a> Choosing the right divisors, the first step in finding the gcd(α, β) by the Euclidean algorithm can be written

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho _{0}=\alpha -\psi _{0}\beta =(\xi -\psi _{0}\eta )\delta ,}</annotation>

</semantics>

</math><img src="./4cbc45d7a01f23c3fa9b97f5d6ca1d20a4639e03.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.793ex; height:2.843ex;" alt="{\displaystyle \rho _{0}=\alpha -\psi _{0}\beta =(\xi -\psi _{0}\eta )\delta ,}" loading="lazy"></dd></dl>

where ψ0 represents the quotient and ρ0 the remainder. Here the quotient and remainder are chosen so that (if nonzero) the remainder has N(ρ0) < N(β) for a "Euclidean function" N defined analogously to the Euclidean functions of <a href="Euclidean_domain" title="Euclidean domain">Euclidean domains</a> in the non-commutative case.<a href="#cite_note-bgv-162">[160]</a> This equation shows that any common right divisor of α and β is likewise a common divisor of the remainder ρ0. The analogous equation for the left divisors would be

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho _{0}=\alpha -\beta \psi _{0}=\delta (\xi -\eta \psi _{0}).}</annotation>

</semantics>

</math><img src="./c98ce45a2ec2ce08f12fba65e4c79ac36d0c4ac1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.793ex; height:2.843ex;" alt="{\displaystyle \rho _{0}=\alpha -\beta \psi _{0}=\delta (\xi -\eta \psi _{0}).}" loading="lazy"></dd></dl>

With either choice, the process is repeated as above until the greatest common right or left divisor is identified. As in the Euclidean domain, the "size" of the remainder ρ0 (formally, its Euclidean function or "norm") must be strictly smaller than β, and there must be only a finite number of possible sizes for ρ0, so that the algorithm is guaranteed to terminate.<a href="#cite_note-entgtrg-163">[161]</a>

Many results for the GCD carry over to noncommutative numbers. For example, <a href="B%C3%A9zout's_identity" title="Bézout's identity">Bézout's identity</a> states that the right gcd(α, β) can be expressed as a linear combination of α and β.<a href="#cite_note-164">[162]</a> In other words, there are numbers σ and τ such that

<msub>

<mtext>right</mtext>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Gamma _{\text{right}}=\sigma \alpha +\tau \beta .}</annotation>

</semantics>

</math><img src="./aa8d8d3f8987285f9825f8a95255112612f8239f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:17.1ex; height:2.843ex;" alt="{\displaystyle \Gamma _{\text{right}}=\sigma \alpha +\tau \beta .}" loading="lazy"></dd></dl>

The analogous identity for the left GCD is nearly the same:

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Gamma _{\text{left}}=\alpha \sigma +\beta \tau .}</annotation>

</semantics>

</math><img src="./7c007a58c690dcbd89cd48db55ed36d92fa9b6e8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.952ex; height:2.509ex;" alt="{\displaystyle \Gamma _{\text{left}}=\alpha \sigma +\beta \tau .}" loading="lazy"></dd></dl>

Bézout's identity can be used to solve Diophantine equations. For instance, one of the standard proofs of <a href="Lagrange's_four-square_theorem" title="Lagrange's four-square theorem">Lagrange's four-square theorem</a>, that every positive integer can be represented as a sum of four squares, is based on quaternion GCDs in this way.<a href="#cite_note-entgtrg-163">[161]</a>

/* start https://en.wikipedia.org/ */

.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .infobox .side-box{font-size:100%}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1237033735">

/* start https://en.wikipedia.org/ */

@media print{body.ns-0 .mw-parser-output .sistersitebox{display:none!important}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}

/* end https://en.wikipedia.org/ */

</style><div class="side-box side-box-right sistersitebox"><style data-mw-deduplicate="TemplateStyles:r1126788409">

/* start https://en.wikipedia.org/ */

.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}

/* end https://en.wikipedia.org/ */

</style>

<div class="side-box-text plainlist"><a href="Wikifunctions" title="Wikifunctions">Wikifunctions</a> has <a href="https://www.wikifunctions.org/wiki/Z13639" class="extiw external" title="f:Z13639">a Euclidean algorithm function</a>.</div></div>

</div>

<ul><li><a href="Euclidean_rhythm" title="Euclidean rhythm">Euclidean rhythm</a>, a method for using the Euclidean algorithm to generate musical rhythms</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><a href="#cite_ref-1">^</a> Some widely used textbooks, such as <a href="I._N._Herstein" class="mw-redirect" title="I. N. Herstein">I. N. Herstein</a>'s Topics in Algebra and <a href="Serge_Lang" title="Serge Lang">Serge Lang</a>'s Algebra, use the term "Euclidean algorithm" to refer to <a href="Euclidean_division" title="Euclidean division">Euclidean division</a>

</li>

<li id="cite_note-143"><a href="#cite_ref-143">^</a> The phrase "ordinary integer" is commonly used for distinguishing usual integers from Gaussian integers, and more generally from <a href="Algebraic_integer" title="Algebraic integer">algebraic integers</a>.

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFLamé1844" class="citation journal cs1 cs1-prop-foreign-lang-source">Lamé, Gabriel (1844). "Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers". Comptes Rendus des Séances de l'Académie des Sciences (in French). 19: 867–870.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFShallit1994" class="citation journal cs1">Shallit, Jeffrey (1994-11-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fhmat.1994.1031">"Origins of the analysis of the Euclidean algorithm"</a>. Historia Mathematica. 21 (4): 401–419. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fhmat.1994.1031">10.1006/hmat.1994.1031</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0315-0860">0315-0860</a>.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <a href="#CITEREFStark1978">Stark 1978</a>, p. 16

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <a href="#CITEREFStark1978">Stark 1978</a>, p. 21

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <a href="#CITEREFLeVeque1996">LeVeque 1996</a>, p. 32

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <a href="#CITEREFLeVeque1996">LeVeque 1996</a>, p. 31

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFGrossman1990" class="citation book cs1">Grossman, J. W. (1990). Discrete Mathematics. New York: Macmillan. p. 213. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-02-348331-8</bdi>.</cite>

</li>

<li id="cite_note-Schroeder_21-9">^ <a href="#cite_ref-Schroeder_21_9-0">a</a> <a href="#cite_ref-Schroeder_21_9-1">b</a> <a href="#CITEREFSchroeder2005">Schroeder 2005</a>, pp. 21–22

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <a href="#CITEREFSchroeder2005">Schroeder 2005</a>, p. 19

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite id="CITEREFOgilvyAnderson1966" class="citation book cs1"><a href="C._Stanley_Ogilvy" title="C. Stanley Ogilvy">Ogilvy, C. S.</a>; Anderson, J. T. (1966). Excursions in number theory. New York: <a href="Oxford_University_Press" title="Oxford University Press">Oxford University Press</a>. pp. 27–29.</cite>

</li>

<li id="cite_note-Schroeder_216-12">^ <a href="#cite_ref-Schroeder_216_12-0">a</a> <a href="#cite_ref-Schroeder_216_12-1">b</a> <a href="#CITEREFSchroeder2005">Schroeder 2005</a>, pp. 216–219

</li>

<li id="cite_note-Leveque_p33-13">^ <a href="#cite_ref-Leveque_p33_13-0">a</a> <a href="#cite_ref-Leveque_p33_13-1">b</a> <a href="#CITEREFLeVeque1996">LeVeque 1996</a>, p. 33

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> <a href="#CITEREFStark1978">Stark 1978</a>, p. 25

</li>

<li id="cite_note-15"><a href="#cite_ref-15">^</a> <a href="#CITEREFOre1948">Ore 1948</a>, pp. 47–48

</li>

<li id="cite_note-16"><a href="#cite_ref-16">^</a> <a href="#CITEREFStark1978">Stark 1978</a>, p. 18

</li>

<li id="cite_note-17"><a href="#cite_ref-17">^</a> <a href="#CITEREFStark1978">Stark 1978</a>, pp. 16–20

</li>

<li id="cite_note-18"><a href="#cite_ref-18">^</a> <a href="#CITEREFKnuth1997">Knuth 1997</a>, p. 320

</li>

<li id="cite_note-Lovasz_2003-19"><a href="#cite_ref-Lovasz_2003_19-0">^</a> <cite id="CITEREFLovászPelikánVesztergombi2003" class="citation book cs1"><a href="L%C3%A1szl%C3%B3_Lov%C3%A1sz" title="László Lovász">Lovász, L.</a>; Pelikán, J.; <a href="Katalin_Vesztergombi" title="Katalin Vesztergombi">Vesztergombi, K.</a> (2003). Discrete Mathematics: Elementary and Beyond. New York: Springer-Verlag. pp. 100–101. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-387-95584-4</bdi>.</cite>

</li>

<li id="cite_note-Kimberling_1983-20"><a href="#cite_ref-Kimberling_1983_20-0">^</a> <cite id="CITEREFKimberling1983" class="citation journal cs1"><a href="Clark_Kimberling" title="Clark Kimberling">Kimberling, C.</a> (1983). "A Visual Euclidean Algorithm". Mathematics Teacher. 76: 108–109.</cite>

</li>

<li id="cite_note-21"><a href="#cite_ref-21">^</a> <cite id="CITEREFDummitFoote2004" class="citation book cs1">Dummit, David S.; Foote, Richard M. (2004). Abstract Algebra. John Wiley & Sons, Inc. pp. 270–271. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-471-43334-7</bdi>.</cite>

</li>

<li id="cite_note-22"><a href="#cite_ref-22">^</a> <a href="#CITEREFKnuth1997">Knuth 1997</a>, pp. 319–320

</li>

<li id="cite_note-23"><a href="#cite_ref-23">^</a> <a href="#CITEREFKnuth1997">Knuth 1997</a>, pp. 318–319

</li>

<li id="cite_note-24"><a href="#cite_ref-24">^</a> <a href="#CITEREFStillwell1997">Stillwell 1997</a>, p. 14

</li>

<li id="cite_note-Ore_least_abs_remainders-25">^ <a href="#cite_ref-Ore_least_abs_remainders_25-0">a</a> <a href="#cite_ref-Ore_least_abs_remainders_25-1">b</a> <a href="#CITEREFOre1948">Ore 1948</a>, p. 43

</li>

<li id="cite_note-Stewart_1964-26">^ <a href="#cite_ref-Stewart_1964_26-0">a</a> <a href="#cite_ref-Stewart_1964_26-1">b</a> <cite id="CITEREFStewart1964" class="citation book cs1">Stewart, B. M. (1964). Theory of Numbers (2nd ed.). New York: Macmillan. pp. 43–44. <a href="LCCN_(identifier)" class="mw-redirect" title="LCCN (identifier)">LCCN</a> <a rel="nofollow" class="external text" href="https://lccn.loc.gov/64010964">64010964</a>.</cite>

</li>

<li id="cite_note-27"><a href="#cite_ref-27">^</a> <cite id="CITEREFLazard1977" class="citation journal cs1 cs1-prop-foreign-lang-source">Lazard, D. (1977). "Le meilleur algorithme d'Euclide pour K[X] et Z". Comptes Rendus de l'Académie des Sciences (in French). 284: 1–4.</cite>

</li>

<li id="cite_note-Knuth,_p._318-28">^ <a href="#cite_ref-Knuth,_p._318_28-0">a</a> <a href="#cite_ref-Knuth,_p._318_28-1">b</a> <a href="#CITEREFKnuth1997">Knuth 1997</a>, p. 318

</li>

<li id="cite_note-Weil_1983-29">^ <a href="#cite_ref-Weil_1983_29-0">a</a> <a href="#cite_ref-Weil_1983_29-1">b</a> <cite id="CITEREFWeil1983" class="citation book cs1"><a href="Andr%C3%A9_Weil" title="André Weil">Weil, A.</a> (1983). Number Theory. Boston: Birkhäuser. pp. 4–6. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-8176-3141-0</bdi>.</cite>

</li>

<li id="cite_note-Jones_1994-30"><a href="#cite_ref-Jones_1994_30-0">^</a> <cite id="CITEREFJones1994" class="citation book cs1">Jones, A. (1994). "Greek mathematics to AD 300". Companion encyclopedia of the history and philosophy of the mathematical sciences. New York: Routledge. pp. 46–48. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-415-09238-8</bdi>.</cite>

</li>

<li id="cite_note-van_der_Waerden_1954-31"><a href="#cite_ref-van_der_Waerden_1954_31-0">^</a> <cite id="CITEREFvan_der_Waerden1954" class="citation book cs1"><a href="Bartel_Leendert_van_der_Waerden" title="Bartel Leendert van der Waerden">van der Waerden, B. L.</a> (1954). <a rel="nofollow" class="external text" href="https://archive.org/details/scienceawakening00waer">Science Awakening</a>. translated by Arnold Dresden. Groningen: P. Noordhoff Ltd. pp. <a rel="nofollow" class="external text" href="https://archive.org/details/scienceawakening00waer/page/114">114–115</a>.</cite>

</li>

<li id="cite_note-32"><a href="#cite_ref-32">^</a> <cite id="CITEREFvon_Fritz1945" class="citation journal cs1">von Fritz, K. (1945). "The Discovery of Incommensurability by Hippasus of Metapontum". Annals of Mathematics. 46 (2): 242–264. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F1969021">10.2307/1969021</a>. <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/1969021">1969021</a>.</cite>

</li>

<li id="cite_note-33"><a href="#cite_ref-33">^</a> <cite id="CITEREFHeath1949" class="citation book cs1"><a href="T._L._Heath" class="mw-redirect" title="T. L. Heath">Heath, T. L.</a> (1949). <a rel="nofollow" class="external text" href="https://archive.org/details/mathematicsinari0000heat">Mathematics in Aristotle</a>. Oxford Press. pp. <a rel="nofollow" class="external text" href="https://archive.org/details/mathematicsinari0000heat/page/80">80–83</a>.</cite>

</li>

<li id="cite_note-34"><a href="#cite_ref-34">^</a> <cite id="CITEREFFowler1987" class="citation book cs1"><a href="David_Fowler_(mathematician)" title="David Fowler (mathematician)">Fowler, D. H.</a> (1987). The Mathematics of Plato's Academy: A New Reconstruction. Oxford: Oxford University Press. pp. 31–66. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-19-853912-6</bdi>.</cite>

</li>

<li id="cite_note-35"><a href="#cite_ref-35">^</a> <cite id="CITEREFBecker1933" class="citation journal cs1">Becker, O. (1933). "Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid". Quellen und Studien zur Geschichte der Mathematik B. 2: 311–333.</cite>

</li>

<li id="cite_note-36"><a href="#cite_ref-36">^</a> <cite id="CITEREFBrezinski1991" class="citation book cs1">Brezinski, Claude (1991). History of continued fractions and Padé approximants. Springer Series in Computational Mathematics. Vol. 12. Springer-Verlag, Berlin. p. <a rel="nofollow" class="external text" href="https://books.google.com/books?id=rxzsCAAAQBAJ&pg=PA6">6</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-642-58169-4">10.1007/978-3-642-58169-4</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>3-540-15286-5</bdi>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1083352">1083352</a>.</cite>

</li>

<li id="cite_note-Stillwell,_p._31-37">^ <a href="#cite_ref-Stillwell,_p._31_37-0">a</a> <a href="#cite_ref-Stillwell,_p._31_37-1">b</a> <a href="#CITEREFStillwell1997">Stillwell 1997</a>, p. 31

</li>

<li id="cite_note-Tattersall,_p._70-38">^ <a href="#cite_ref-Tattersall,_p._70_38-0">a</a> <a href="#cite_ref-Tattersall,_p._70_38-1">b</a> <a href="#CITEREFTattersall2005">Tattersall 2005</a>, p. 70

</li>

<li id="cite_note-39"><a href="#cite_ref-39">^</a> <a href="#CITEREFRosen2000">Rosen 2000</a>, pp. 86–87

</li>

<li id="cite_note-40"><a href="#cite_ref-40">^</a> <a href="#CITEREFOre1948">Ore 1948</a>, pp. 247–248

</li>

<li id="cite_note-41"><a href="#cite_ref-41">^</a> <a href="#CITEREFTattersall2005">Tattersall 2005</a>, pp. 72, 184–185

</li>

<li id="cite_note-42"><a href="#cite_ref-42">^</a> <cite id="CITEREFSaunderson1740" class="citation book cs1">Saunderson, Nicholas (1740). <a rel="nofollow" class="external text" href="http://www.e-rara.ch/zut/content/structure/2440626">The Elements of Algebra in Ten Books</a>. University of Cambridge Press. Retrieved 1 November 2016.</cite>

</li>

<li id="cite_note-43"><a href="#cite_ref-43">^</a> <a href="#CITEREFTattersall2005">Tattersall 2005</a>, pp. 72–76

</li>

<li id="cite_note-Gauss_1832-44">^ <a href="#cite_ref-Gauss_1832_44-0">a</a> <a href="#cite_ref-Gauss_1832_44-1">b</a> <cite id="CITEREFGauss1832" class="citation journal cs1"><a href="Carl_Friedrich_Gauss" title="Carl Friedrich Gauss">Gauss, C. F.</a> (1832). "Theoria residuorum biquadraticorum". Comm. Soc. Reg. Sci. Gött. Rec. 4.</cite> Reprinted in <cite id="CITEREFGauss2011" class="citation book cs1">Gauss, C. F. (2011). "Theoria residuorum biquadraticorum commentatio prima". Werke. Vol. 2. Cambridge Univ. Press. pp. 65–92. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1017%2FCBO9781139058230.004">10.1017/CBO9781139058230.004</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781139058230</bdi>.</cite> and <cite id="CITEREFGauss2011" class="citation book cs1">Gauss, C. F. (2011). "Theoria residuorum biquadraticorum commentatio secunda". Werke. Vol. 2. Cambridge Univ. Press. pp. 93–148. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1017%2FCBO9781139058230.005">10.1017/CBO9781139058230.005</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781139058230</bdi>.</cite>

</li>

<li id="cite_note-45"><a href="#cite_ref-45">^</a> <a href="#CITEREFStillwell1997">Stillwell 1997</a>, pp. 31–32

</li>

<li id="cite_note-46"><a href="#cite_ref-46">^</a> <a href="#CITEREFLejeune_Dirichlet1894">Lejeune Dirichlet 1894</a>, pp. 29–31

</li>

<li id="cite_note-47"><a href="#cite_ref-47">^</a> <a href="Richard_Dedekind" title="Richard Dedekind">Richard Dedekind</a> in <a href="#CITEREFLejeune_Dirichlet1894">Lejeune Dirichlet 1894</a>, Supplement XI

</li>

<li id="cite_note-48"><a href="#cite_ref-48">^</a> <a href="#CITEREFStillwell2003">Stillwell 2003</a>, pp. 41–42

</li>

<li id="cite_note-49"><a href="#cite_ref-49">^</a> <cite id="CITEREFSturm1829" class="citation journal cs1 cs1-prop-foreign-lang-source"><a href="Jacques_Charles_Fran%C3%A7ois_Sturm" title="Jacques Charles François Sturm">Sturm, C.</a> (1829). "Mémoire sur la résolution des équations numériques". Bull. Des sciences de Férussac (in French). 11: 419–422.</cite>

</li>

<cite id="CITEREFFergusonForcade1979" class="citation journal cs1"><a href="Helaman_Ferguson" title="Helaman Ferguson">Ferguson, H. R. P.</a>; Forcade, R. W. (1979). <a rel="nofollow" class="external text" href="https://doi.org/10.1090%2FS0273-0979-1979-14691-3">"Generalization of the Euclidean algorithm for real numbers to all dimensions higher than two"</a>. Bulletin of the American Mathematical Society. New Series. 1 (6): 912–914. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090%2FS0273-0979-1979-14691-3">10.1090/S0273-0979-1979-14691-3</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0546316">0546316</a>.</cite>

</li>

<li id="cite_note-51"><a href="#cite_ref-51">^</a> <cite id="CITEREFPeterson2002" class="citation journal cs1">Peterson, I. (12 August 2002). <a rel="nofollow" class="external text" href="http://www.sciencenews.org/view/generic/id/172/title/Math_Trek__Jazzing_Up_Euclids_Algorithm">"Jazzing Up Euclid's Algorithm"</a>. ScienceNews.</cite>

</li>

<li id="cite_note-52"><a href="#cite_ref-52">^</a> <cite id="CITEREFCipra2000" class="citation journal cs1"><a href="Barry_Arthur_Cipra" title="Barry Arthur Cipra">Cipra, Barry Arthur</a> (16 May 2000). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20160922144038/https://www.siam.org/pdf/news/637.pdf">"The Best of the 20th Century: Editors Name Top 10 Algorithms"</a> (PDF). SIAM News. 33 (4). <a href="Society_for_Industrial_and_Applied_Mathematics" title="Society for Industrial and Applied Mathematics">Society for Industrial and Applied Mathematics</a>. Archived from <a rel="nofollow" class="external text" href="https://www.siam.org/pdf/news/637.pdf">the original</a> (PDF) on 22 September 2016. Retrieved 19 July 2016.</cite>

</li>

<li id="cite_note-53"><a href="#cite_ref-53">^</a> <cite id="CITEREFColeDavie1969" class="citation journal cs1">Cole, A. J.; Davie, A. J. T. (1969). "A game based on the Euclidean algorithm and a winning strategy for it". Math. Gaz. 53 (386): 354–357. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F3612461">10.2307/3612461</a>. <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/3612461">3612461</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:125164797">125164797</a>.</cite>

</li>

<li id="cite_note-54"><a href="#cite_ref-54">^</a> <cite id="CITEREFSpitznagel1973" class="citation journal cs1">Spitznagel, E. L. (1973). "Properties of a game based on Euclid's algorithm". Math. Mag. 46 (2): 87–92. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2689037">10.2307/2689037</a>. <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2689037">2689037</a>.</cite>

</li>

<li id="cite_note-55"><a href="#cite_ref-55">^</a> <a href="#CITEREFRosen2000">Rosen 2000</a>, p. 95

</li>

<li id="cite_note-56"><a href="#cite_ref-56">^</a> <cite id="CITEREFRoberts1977" class="citation book cs1">Roberts, J. (1977). <a rel="nofollow" class="external text" href="https://archive.org/details/Elementary_00_Robe/page/1">Elementary Number Theory: A Problem Oriented Approach</a>. Cambridge, MA: <a href="MIT_Press" title="MIT Press">MIT Press</a>. pp. <a rel="nofollow" class="external text" href="https://archive.org/details/Elementary_00_Robe/page/1">1–8</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-262-68028-9</bdi>.</cite>

</li>

<li id="cite_note-57"><a href="#cite_ref-57">^</a> <cite id="CITEREFJonesJones1998" class="citation book cs1">Jones, G. A.; Jones, J. M. (1998). "Bezout's Identity". Elementary Number Theory. New York: Springer-Verlag. pp. 7–11.</cite>

</li>

<li id="cite_note-58"><a href="#cite_ref-58">^</a> <a href="#CITEREFRosen2000">Rosen 2000</a>, p. 81

</li>

<li id="cite_note-59"><a href="#cite_ref-59">^</a> <a href="#CITEREFCohn1980">Cohn 1980</a>, p. 104

</li>

<li id="cite_note-60"><a href="#cite_ref-60">^</a> <a href="#CITEREFRosen2000">Rosen 2000</a>, p. 91

</li>

<li id="cite_note-61"><a href="#cite_ref-61">^</a> <a href="#CITEREFSchroeder2005">Schroeder 2005</a>, p. 23

</li>

<li id="cite_note-62"><a href="#cite_ref-62">^</a> <a href="#CITEREFRosen2000">Rosen 2000</a>, pp. 90–93

</li>

<li id="cite_note-Koshy_2002-63">^ <a href="#cite_ref-Koshy_2002_63-0">a</a> <a href="#cite_ref-Koshy_2002_63-1">b</a> <cite id="CITEREFKoshy2002" class="citation book cs1">Koshy, T. (2002). Elementary Number Theory with Applications. Burlington, MA: Harcourt/Academic Press. pp. 167–169. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-12-421171-2</bdi>.</cite>

</li>

<li id="cite_note-Bach_1996-64"><a href="#cite_ref-Bach_1996_64-0">^</a> <cite id="CITEREFBachShallit1996" class="citation book cs1"><a href="Eric_Bach" title="Eric Bach">Bach, E.</a>; <a href="Jeffrey_Shallit" title="Jeffrey Shallit">Shallit, J.</a> (1996). Algorithmic number theory. Cambridge, MA: MIT Press. pp. 70–73. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-262-02405-5</bdi>.</cite>

</li>

<li id="cite_note-65"><a href="#cite_ref-65">^</a> <a href="#CITEREFStark1978">Stark 1978</a>, pp. 26–36

</li>

<li id="cite_note-Ore,_p._44-66">^ <a href="#cite_ref-Ore,_p._44_66-0">a</a> <a href="#cite_ref-Ore,_p._44_66-1">b</a> <a href="#CITEREFOre1948">Ore 1948</a>, p. 44

</li>

<li id="cite_note-67"><a href="#cite_ref-67">^</a> <a href="#CITEREFStark1978">Stark 1978</a>, pp. 281–292

</li>

<li id="cite_note-68"><a href="#cite_ref-68">^</a> <a href="#CITEREFRosen2000">Rosen 2000</a>, pp. 119–125

</li>

<li id="cite_note-69"><a href="#cite_ref-69">^</a> <a href="#CITEREFSchroeder2005">Schroeder 2005</a>, pp. 106–107

</li>

<li id="cite_note-70"><a href="#cite_ref-70">^</a> <a href="#CITEREFSchroeder2005">Schroeder 2005</a>, pp. 108–109

</li>

<li id="cite_note-71"><a href="#cite_ref-71">^</a> <a href="#CITEREFRosen2000">Rosen 2000</a>, pp. 120–121

</li>

<li id="cite_note-72"><a href="#cite_ref-72">^</a> <a href="#CITEREFStark1978">Stark 1978</a>, p. 47

</li>

<li id="cite_note-73"><a href="#cite_ref-73">^</a> <a href="#CITEREFSchroeder2005">Schroeder 2005</a>, pp. 107–109

</li>

<li id="cite_note-74"><a href="#cite_ref-74">^</a> <a href="#CITEREFStillwell1997">Stillwell 1997</a>, pp. 186–187

</li>

<li id="cite_note-75"><a href="#cite_ref-75">^</a> <a href="#CITEREFSchroeder2005">Schroeder 2005</a>, p. 134

</li>

<li id="cite_note-76"><a href="#cite_ref-76">^</a> <cite id="CITEREFMoon2005" class="citation book cs1">Moon, T. K. (2005). Error Correction Coding: Mathematical Methods and Algorithms. John Wiley and Sons. p. 266. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-471-64800-0</bdi>.</cite>

</li>

<li id="cite_note-77"><a href="#cite_ref-77">^</a> <a href="#CITEREFRosen2000">Rosen 2000</a>, pp. 143–170

</li>

<li id="cite_note-78"><a href="#cite_ref-78">^</a> <a href="#CITEREFSchroeder2005">Schroeder 2005</a>, pp. 194–195

</li>

<li id="cite_note-79"><a href="#cite_ref-79">^</a> <cite id="CITEREFGrahamKnuthPatashnik1989" class="citation book cs1"><a href="Ronald_Graham" title="Ronald Graham">Graham, R.</a>; <a href="Donald_Knuth" title="Donald Knuth">Knuth, D. E.</a>; <a href="Oren_Patashnik" title="Oren Patashnik">Patashnik, O.</a> (1989). Concrete mathematics. Addison-Wesley. p. 123.</cite>

</li>

<li id="cite_note-Vinogradov_1954-80"><a href="#cite_ref-Vinogradov_1954_80-0">^</a> <cite id="CITEREFVinogradov1954" class="citation book cs1"><a href="Ivan_Matveyevich_Vinogradov" class="mw-redirect" title="Ivan Matveyevich Vinogradov">Vinogradov, I. M.</a> (1954). <a rel="nofollow" class="external text" href="https://archive.org/details/elementsofnumber0000vino">Elements of Number Theory</a>. New York: Dover. pp. <a rel="nofollow" class="external text" href="https://archive.org/details/elementsofnumber0000vino/page/3">3–13</a>.</cite>

</li>

<li id="cite_note-81"><a href="#cite_ref-81">^</a> <a href="#CITEREFCrandallPomerance2001">Crandall & Pomerance 2001</a>, pp. 225–349

</li>

<li id="cite_note-82"><a href="#cite_ref-82">^</a> <a href="#CITEREFKnuth1997">Knuth 1997</a>, pp. 369–371

</li>

<li id="cite_note-83"><a href="#cite_ref-83">^</a> <cite id="CITEREFShor1997" class="citation journal cs1"><a href="Peter_Shor" title="Peter Shor">Shor, P. W.</a> (1997). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Journal on Scientific and Statistical Computing. 26 (5): 1484–1509. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/9508027">quant-ph/9508027</a>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1995quant.ph..8027S">1995quant.ph..8027S</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2Fs0097539795293172">10.1137/s0097539795293172</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2337707">2337707</a>.</cite>

</li>

<li id="cite_note-84"><a href="#cite_ref-84">^</a> <cite id="CITEREFDixon1981" class="citation journal cs1">Dixon, J. D. (1981). <a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2007743">"Asymptotically fast factorization of integers"</a>. Math. Comput. 36 (153): 255–260. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2007743">10.2307/2007743</a>. <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2007743">2007743</a>.</cite>

</li>

<li id="cite_note-85"><a href="#cite_ref-85">^</a> <cite id="CITEREFLenstra1987" class="citation journal cs1"><a href="Hendrik_Lenstra" title="Hendrik Lenstra">Lenstra, H. W. Jr.</a> (1987). "Factoring integers with elliptic curves". Annals of Mathematics. 126 (3): 649–673. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F1971363">10.2307/1971363</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/1887%2F2140">1887/2140</a>. <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/1971363">1971363</a>.</cite>

</li>

<li id="cite_note-86"><a href="#cite_ref-86">^</a> <a href="#CITEREFKnuth1997">Knuth 1997</a>, pp. 380–384

</li>

<li id="cite_note-87"><a href="#cite_ref-87">^</a> <a href="#CITEREFKnuth1997">Knuth 1997</a>, pp. 339–364

</li>

<li id="cite_note-88"><a href="#cite_ref-88">^</a> <cite id="CITEREFReynaud1811" class="citation book cs1">Reynaud, A.-A.-L. (1811). <a rel="nofollow" class="external text" href="https://archive.org/details/bub_gb_YySjvK7oudIC">Traité d'arithmétique à l'usage des élèves qui se destinent à l'École Polytechnique</a> (6th ed.). Paris: Courcier. Note 60, p. 34.</cite> As cited by <a href="#CITEREFShallit1994">Shallit (1994)</a>.

</li>

<li id="cite_note-89"><a href="#cite_ref-89">^</a> <cite id="CITEREFFinck1841" class="citation book cs1 cs1-prop-foreign-lang-source">Finck, P.-J.-E. (1841). Traité élémentaire d'arithmétique à l'usage des candidats aux écoles spéciales (in French). Derivaux.</cite>

</li>

<li id="cite_note-FOOTNOTEShallit1994-90">^ <a href="#cite_ref-FOOTNOTEShallit1994_90-0">a</a> <a href="#cite_ref-FOOTNOTEShallit1994_90-1">b</a> <a href="#CITEREFShallit1994">Shallit 1994</a>.

</li>

<li id="cite_note-91"><a href="#cite_ref-91">^</a> <cite id="CITEREFLamé1844" class="citation journal cs1 cs1-prop-foreign-lang-source"><a href="Gabriel_Lam%C3%A9" title="Gabriel Lamé">Lamé, G.</a> (1844). "Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers". Comptes Rendus de l'Académie des Sciences (in French). 19: 867–870.</cite>

</li>

<li id="cite_note-92"><a href="#cite_ref-92">^</a> <cite id="CITEREFGrossman1924" class="citation journal cs1">Grossman, H. (1924). "On the Number of Divisions in Finding a G.C.D". The American Mathematical Monthly. 31 (9): 443. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2298146">10.2307/2298146</a>. <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2298146">2298146</a>.</cite>

</li>

<li id="cite_note-93"><a href="#cite_ref-93">^</a> <cite id="CITEREFHonsberger1976" class="citation book cs1"><a href="Ross_Honsberger" title="Ross Honsberger">Honsberger, R.</a> (1976). Mathematical Gems II. The <a href="Mathematical_Association_of_America" title="Mathematical Association of America">Mathematical Association of America</a>. pp. 54–57. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-88385-302-7</bdi>.</cite>

</li>

<li id="cite_note-Knuth-257-261-94">^ <a href="#cite_ref-Knuth-257-261_94-0">a</a> <a href="#cite_ref-Knuth-257-261_94-1">b</a> <a href="#CITEREFKnuth1997">Knuth 1997</a>, pp. 257–261

</li>

<li id="cite_note-Crandall_2001-95">^ <a href="#cite_ref-Crandall_2001_95-0">a</a> <a href="#cite_ref-Crandall_2001_95-1">b</a> <a href="#cite_ref-Crandall_2001_95-2">c</a> <a href="#CITEREFCrandallPomerance2001">Crandall & Pomerance 2001</a>, pp. 77–79, 81–85, 425–431

</li>

<li id="cite_note-Moller08-96">^ <a href="#cite_ref-Moller08_96-0">a</a> <a href="#cite_ref-Moller08_96-1">b</a> <cite id="CITEREFMöller2008" class="citation journal cs1">Möller, N. (2008). <a rel="nofollow" class="external text" href="http://www.lysator.liu.se/~nisse/archive/sgcd.pdf">"On Schönhage's algorithm and subquadratic integer gcd computation"</a> (PDF). Mathematics of Computation. 77 (261): 589–607. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2008MaCom..77..589M">2008MaCom..77..589M</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090%2FS0025-5718-07-02017-0">10.1090/S0025-5718-07-02017-0</a>.</cite>

</li>

<li id="cite_note-Knuth,_p._344-97">^ <a href="#cite_ref-Knuth,_p._344_97-0">a</a> <a href="#cite_ref-Knuth,_p._344_97-1">b</a> <a href="#cite_ref-Knuth,_p._344_97-2">c</a> <a href="#CITEREFKnuth1997">Knuth 1997</a>, p. 344

</li>

<li id="cite_note-98"><a href="#cite_ref-98">^</a> <a href="#CITEREFOre1948">Ore 1948</a>, p. 45

</li>

<li id="cite_note-Knuth,_p._343-99">^ <a href="#cite_ref-Knuth,_p._343_99-0">a</a> <a href="#cite_ref-Knuth,_p._343_99-1">b</a> <a href="#CITEREFKnuth1997">Knuth 1997</a>, p. 343

</li>

<li id="cite_note-100"><a href="#cite_ref-100">^</a> <a href="#CITEREFMollin2008">Mollin 2008</a>, p. 21

</li>

<li id="cite_note-101"><a href="#cite_ref-101">^</a> <a href="#CITEREFLeVeque1996">LeVeque 1996</a>, p. 35

</li>

<li id="cite_note-102"><a href="#cite_ref-102">^</a> <a href="#CITEREFMollin2008">Mollin 2008</a>, pp. 21–22

</li>

<li id="cite_note-103"><a href="#cite_ref-103">^</a> <a href="#CITEREFKnuth1997">Knuth 1997</a>, p. 353

</li>

<li id="cite_note-104"><a href="#cite_ref-104">^</a> <a href="#CITEREFKnuth1997">Knuth 1997</a>, p. 357

</li>

<li id="cite_note-105"><a href="#cite_ref-105">^</a> <cite id="CITEREFTonkov1974" class="citation journal cs1">Tonkov, T. (1974). <a rel="nofollow" class="external text" href="https://doi.org/10.4064%2Faa-26-1-47-57">"On the average length of finite continued fractions"</a>. Acta Arithmetica. 26 (1): 47–57. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.4064%2Faa-26-1-47-57">10.4064/aa-26-1-47-57</a>.</cite>

</li>

<cite id="CITEREFKnuth1976" class="citation journal cs1"><a href="Donald_E._Knuth" class="mw-redirect" title="Donald E. Knuth">Knuth, Donald E.</a> (1976). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0898-1221%2876%2990025-0">"Evaluation of Porter's constant"</a>. Computers & Mathematics with Applications. 2 (2): 137–139. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0898-1221%2876%2990025-0">10.1016/0898-1221(76)90025-0</a>.</cite>

</li>

<li id="cite_note-107"><a href="#cite_ref-107">^</a> <cite id="CITEREFPorter1975" class="citation journal cs1">Porter, J. W. (1975). "On a Theorem of Heilbronn". <a href="Mathematika" title="Mathematika">Mathematika</a>. 22 (1): 20–28. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1112%2FS0025579300004459">10.1112/S0025579300004459</a>.</cite>

</li>

<li id="cite_note-108"><a href="#cite_ref-108">^</a> <cite id="CITEREFKnuth1976" class="citation journal cs1"><a href="Donald_Knuth" title="Donald Knuth">Knuth, D. E.</a> (1976). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0898-1221%2876%2990025-0">"Evaluation of Porter's Constant"</a>. Computers and Mathematics with Applications. 2 (2): 137–139. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0898-1221%2876%2990025-0">10.1016/0898-1221(76)90025-0</a>.</cite>

</li>

<li id="cite_note-109"><a href="#cite_ref-109">^</a> <cite id="CITEREFDixon1970" class="citation journal cs1">Dixon, J. D. (1970). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0022-314X%2870%2990044-2">"The Number of Steps in the Euclidean Algorithm"</a>. J. Number Theory. 2 (4): 414–422. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1970JNT.....2..414D">1970JNT.....2..414D</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0022-314X%2870%2990044-2">10.1016/0022-314X(70)90044-2</a>.</cite>

</li>

<li id="cite_note-110"><a href="#cite_ref-110">^</a> <cite id="CITEREFHeilbronn1969" class="citation book cs1"><a href="Hans_Heilbronn" title="Hans Heilbronn">Heilbronn, H. A.</a> (1969). "On the Average Length of a Class of Finite Continued Fractions". In Paul Turán (ed.). Number Theory and Analysis. New York: Plenum. pp. 87–96. <a href="LCCN_(identifier)" class="mw-redirect" title="LCCN (identifier)">LCCN</a> <a rel="nofollow" class="external text" href="https://lccn.loc.gov/76016027">76016027</a>.</cite>

</li>

<li id="cite_note-111"><a href="#cite_ref-111">^</a> <a href="#CITEREFKnuth1997">Knuth 1997</a>, p. 354

</li>

<li id="cite_note-Norton_1990-112">^ <a href="#cite_ref-Norton_1990_112-0">a</a> <a href="#cite_ref-Norton_1990_112-1">b</a> <cite id="CITEREFNorton1990" class="citation journal cs1">Norton, G. H. (1990). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0747-7171%2808%2980036-3">"On the Asymptotic Analysis of the Euclidean Algorithm"</a>. Journal of Symbolic Computation. 10 (1): 53–58. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0747-7171%2808%2980036-3">10.1016/S0747-7171(08)80036-3</a>.</cite>

</li>

<li id="cite_note-113"><a href="#cite_ref-113">^</a> <a href="#CITEREFKnuth1997">Knuth 1997</a>, p. 355

</li>

<li id="cite_note-114"><a href="#cite_ref-114">^</a> <a href="#CITEREFKnuth1997">Knuth 1997</a>, p. 356

</li>

<li id="cite_note-115"><a href="#cite_ref-115">^</a> <a href="#CITEREFKnuth1997">Knuth 1997</a>, p. 352

</li>

<li id="cite_note-116"><a href="#cite_ref-116">^</a> <cite id="CITEREFWagon1999" class="citation book cs1"><a href="Stan_Wagon" title="Stan Wagon">Wagon, S.</a> (1999). Mathematica in Action. New York: Springer-Verlag. pp. 335–336. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-387-98252-3</bdi>.</cite>

</li>

<li id="cite_note-117"><a href="#cite_ref-117">^</a> <a href="#CITEREFCohen1993">Cohen 1993</a>, p. 14

</li>

<li id="cite_note-118"><a href="#cite_ref-118">^</a> <a href="#CITEREFCohen1993">Cohen 1993</a>, pp. 14–15, 17–18

</li>

<cite id="CITEREFSorenson2004" class="citation book cs1">Sorenson, Jonathan P. (2004). "An analysis of the generalized binary GCD algorithm". <a rel="nofollow" class="external text" href="https://books.google.com/books?id=udr3tHHwBl0C&pg=PA327">High primes and misdemeanours: lectures in honour of the 60th birthday of Hugh Cowie Williams</a>. Fields Institute Communications. Vol. 41. Providence, RI: American Mathematical Society. pp. 327–340. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780821887592</bdi>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2076257">2076257</a>. <q>The algorithms that are used the most in practice today [for computing greatest common divisors] are probably the binary algorithm and Euclid's algorithm for smaller numbers, and either Lehmer's algorithm or Lebealean's version of the k-ary GCD algorithm for larger numbers.</q></cite>

</li>

<li id="cite_note-120"><a href="#cite_ref-120">^</a> <a href="#CITEREFKnuth1997">Knuth 1997</a>, pp. 321–323

</li>

<li id="cite_note-121"><a href="#cite_ref-121">^</a> <cite id="CITEREFStein1967" class="citation journal cs1">Stein, J. (1967). "Computational problems associated with Racah algebra". Journal of Computational Physics. 1 (3): 397–405. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1967JCoPh...1..397S">1967JCoPh...1..397S</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0021-9991%2867%2990047-2">10.1016/0021-9991(67)90047-2</a>.</cite>

</li>

<li id="cite_note-122"><a href="#cite_ref-122">^</a> <a href="#CITEREFKnuth1997">Knuth 1997</a>, p. 328

</li>

<li id="cite_note-123"><a href="#cite_ref-123">^</a> <cite id="CITEREFLehmer1938" class="citation journal cs1"><a href="Derrick_Henry_Lehmer" class="mw-redirect" title="Derrick Henry Lehmer">Lehmer, D. H.</a> (1938). "Euclid's Algorithm for Large Numbers". The American Mathematical Monthly. 45 (4): 227–233. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2302607">10.2307/2302607</a>. <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2302607">2302607</a>.</cite>

</li>

<li id="cite_note-124"><a href="#cite_ref-124">^</a> <cite id="CITEREFSorenson1994" class="citation journal cs1">Sorenson, J. (1994). "Two fast GCD algorithms". J. Algorithms. 16 (1): 110–144. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjagm.1994.1006">10.1006/jagm.1994.1006</a>.</cite>

</li>

<li id="cite_note-125"><a href="#cite_ref-125">^</a> <cite id="CITEREFWeber1995" class="citation journal cs1">Weber, K. (1995). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F200979.201042">"The accelerated GCD algorithm"</a>. ACM Trans. Math. Softw. 21 (1): 111–122. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F200979.201042">10.1145/200979.201042</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:14934919">14934919</a>.</cite>

</li>

<li id="cite_note-126"><a href="#cite_ref-126">^</a> <cite id="CITEREFAhoHopcroftUllman1974" class="citation book cs1"><a href="Alfred_Aho" title="Alfred Aho">Aho, A.</a>; <a href="John_Hopcroft" title="John Hopcroft">Hopcroft, J.</a>; <a href="Jeffrey_Ullman" title="Jeffrey Ullman">Ullman, J.</a> (1974). <a rel="nofollow" class="external text" href="https://archive.org/details/designanalysisof00ahoarich/page/300">The Design and Analysis of Computer Algorithms</a>. New York: Addison–Wesley. pp. <a rel="nofollow" class="external text" href="https://archive.org/details/designanalysisof00ahoarich/page/300">300–310</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-201-00029-6</bdi>.</cite>

</li>

<li id="cite_note-127"><a href="#cite_ref-127">^</a> <cite id="CITEREFSchönhage1971" class="citation journal cs1 cs1-prop-foreign-lang-source"><a href="Arnold_Sch%C3%B6nhage" title="Arnold Schönhage">Schönhage, A.</a> (1971). "Schnelle Berechnung von Kettenbruchentwicklungen". Acta Informatica (in German). 1 (2): 139–144. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF00289520">10.1007/BF00289520</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:34561609">34561609</a>.</cite>

</li>

<li id="cite_note-128"><a href="#cite_ref-128">^</a> <cite id="CITEREFCesari1998" class="citation book cs1">Cesari, G. (1998). "Parallel implementation of Schönhage's integer GCD algorithm". In G. Buhler (ed.). Algorithmic Number Theory: Proc. ANTS-III, Portland, OR. Lecture Notes in Computer Science. Vol. 1423. New York: Springer-Verlag. pp. 64–76.</cite>

</li>

<li id="cite_note-129"><a href="#cite_ref-129">^</a> <cite id="CITEREFStehléZimmermann2005" class="citation book cs1">Stehlé, D.; Zimmermann, P. (2005). "<a href="Gal's_accurate_tables" title="Gal's accurate tables">Gal's accurate tables</a> method revisited". Proceedings of the 17th IEEE Symposium on Computer Arithmetic (ARITH-17). Los Alamitos, CA: <a href="IEEE_Computer_Society_Press" class="mw-redirect" title="IEEE Computer Society Press">IEEE Computer Society Press</a>.</cite>

</li>

<li id="cite_note-Lang_1984-130">^ <a href="#cite_ref-Lang_1984_130-0">a</a> <a href="#cite_ref-Lang_1984_130-1">b</a> <a href="#cite_ref-Lang_1984_130-2">c</a> <cite id="CITEREFLang1984" class="citation book cs1"><a href="Serge_Lang" title="Serge Lang">Lang, S.</a> (1984). Algebra (2nd ed.). Menlo Park, CA: Addison–Wesley. pp. 190–194. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-201-05487-6</bdi>.</cite>

</li>

<li id="cite_note-weinberger-131">^ <a href="#cite_ref-weinberger_131-0">a</a> <a href="#cite_ref-weinberger_131-1">b</a> <cite id="CITEREFWeinberger1973" class="citation journal cs1">Weinberger, P. (1973). "On Euclidean rings of algebraic integers". Proc. Sympos. Pure Math. Proceedings of Symposia in Pure Mathematics. 24. Providence, Rhode Island: 321–332. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090%2Fpspum%2F024%2F0337902">10.1090/pspum/024/0337902</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780821814246</bdi>.</cite>

</li>

<li id="cite_note-stillwell151-152-132">^ <a href="#cite_ref-stillwell151-152_132-0">a</a> <a href="#cite_ref-stillwell151-152_132-1">b</a> <a href="#cite_ref-stillwell151-152_132-2">c</a> <a href="#CITEREFStillwell2003">Stillwell 2003</a>, pp. 151–152

</li>

<li id="cite_note-133"><a href="#cite_ref-133">^</a> <cite id="CITEREFBoyerMerzbach1991" class="citation book cs1">Boyer, C. B.; <a href="Uta_Merzbach" title="Uta Merzbach">Merzbach, U. C.</a> (1991). <a rel="nofollow" class="external text" href="https://archive.org/details/historyofmathema00boye/page/116">A History of Mathematics</a> (2nd ed.). New York: Wiley. pp. <a rel="nofollow" class="external text" href="https://archive.org/details/historyofmathema00boye/page/116">116–117</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-471-54397-7</bdi>.</cite>

</li>

<li id="cite_note-134"><a href="#cite_ref-134">^</a> <cite id="CITEREFCajori1894" class="citation book cs1"><a href="Florian_Cajori" title="Florian Cajori">Cajori, F</a> (1894). <a rel="nofollow" class="external text" href="https://archive.org/details/in.ernet.dli.2015.73802">A History of Mathematics</a>. New York: Macmillan. p. <a rel="nofollow" class="external text" href="https://archive.org/details/in.ernet.dli.2015.73802/page/n78">70</a>.</cite> Reprinted, Dover Publications, 2004, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-486-43874-0</bdi>

</li>

<li id="cite_note-135"><a href="#cite_ref-135">^</a> <cite id="CITEREFJoux2009" class="citation book cs1">Joux, Antoine (2009). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=buQajqt-_iUC&pg=PA33">Algorithmic Cryptanalysis</a>. CRC Press. p. 33. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781420070033</bdi>.</cite>

</li>

<li id="cite_note-136"><a href="#cite_ref-136">^</a> <cite id="CITEREFFuksTabachnikov2007" class="citation book cs1">Fuks, D. B.; <a href="Sergei_Tabachnikov" title="Sergei Tabachnikov">Tabachnikov, Serge</a> (2007). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=IiG9AwAAQBAJ&pg=PA13">Mathematical Omnibus: Thirty Lectures on Classic Mathematics</a>. American Mathematical Society. p. 13. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780821843161</bdi>.</cite>

</li>

<li id="cite_note-137"><a href="#cite_ref-137">^</a> <cite id="CITEREFDarling2004" class="citation book cs1"><a href="David_J._Darling" title="David J. Darling">Darling, David</a> (2004). "Khintchine's constant". <a rel="nofollow" class="external text" href="https://books.google.com/books?id=HrOxRdtYYaMC&pg=PA175">The Universal Book of Mathematics: From Abracadabra to Zeno's Paradoxes</a>. John Wiley & Sons. p. 175. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780471667001</bdi>.</cite>

</li>

<li id="cite_note-138"><a href="#cite_ref-138">^</a> <cite id="CITEREFWilliams2010" class="citation book cs1">Williams, Colin P. (2010). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=QE8S--WjIFwC&pg=PA277">Explorations in Quantum Computing</a>. Springer. pp. 277–278. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781846288876</bdi>.</cite>

</li>

<li id="cite_note-139"><a href="#cite_ref-139">^</a> <a href="#CITEREFCoxLittleO'Shea1997">Cox, Little & O'Shea 1997</a>, pp. 37–46

</li>

<li id="cite_note-140"><a href="#cite_ref-140">^</a> <a href="#CITEREFSchroeder2005">Schroeder 2005</a>, pp. 254–259

</li>

<li id="cite_note-141"><a href="#cite_ref-141">^</a> <cite id="CITEREFGrattan-Guinness1990" class="citation book cs1"><a href="Ivor_Grattan-Guinness" title="Ivor Grattan-Guinness">Grattan-Guinness, Ivor</a> (1990). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=_GgioErrbW8C&pg=PA1148">Convolutions in French Mathematics, 1800-1840: From the Calculus and Mechanics to Mathematical Analysis and Mathematical Physics. Volume II: The Turns</a>. Science Networks: Historical Studies. Vol. 3. Basel, Boston, Berlin: Birkhäuser. p. 1148. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783764322380</bdi>. <q>Our subject here is the 'Sturm sequence' of functions defined from a function and its derivative by means of Euclid's algorithm, in order to calculate the number of real roots of a polynomial within a given interval</q></cite>

</li>

<li id="cite_note-142"><a href="#cite_ref-142">^</a> <cite id="CITEREFHairerNørsettWanner1993" class="citation book cs1">Hairer, Ernst; Nørsett, Syvert P.; Wanner, Gerhard (1993). "The Routh–Hurwitz Criterion". <a rel="nofollow" class="external text" href="https://books.google.com/books?id=F93u7VcSRyYC&pg=PA81">Solving Ordinary Differential Equations I: Nonstiff Problems</a>. Springer Series in Computational Mathematics. Vol. 8 (2nd ed.). Springer. pp. 81ff. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783540566700</bdi>.</cite>

</li>

<li id="cite_note-Stillwell_2003-144">^ <a href="#cite_ref-Stillwell_2003_144-0">a</a> <a href="#cite_ref-Stillwell_2003_144-1">b</a> <a href="#cite_ref-Stillwell_2003_144-2">c</a> <a href="#CITEREFStillwell2003">Stillwell 2003</a>, pp. 101–116

</li>

<li id="cite_note-hensley-145">^ <a href="#cite_ref-hensley_145-0">a</a> <a href="#cite_ref-hensley_145-1">b</a> <a href="#cite_ref-hensley_145-2">c</a> <cite id="CITEREFHensley2006" class="citation book cs1">Hensley, Doug (2006). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=k3PVXFkweKgC&pg=PA26">Continued Fractions</a>. World Scientific. p. 26. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9789812564771</bdi>.</cite>

</li>

<li id="cite_note-146"><a href="#cite_ref-146">^</a> <cite id="CITEREFDedekind1996" class="citation book cs1"><a href="Richard_Dedekind" title="Richard Dedekind">Dedekind, Richard</a> (1996). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=KZRBabJY4ewC&pg=PA222">Theory of Algebraic Integers</a>. Cambridge Mathematical Library. Cambridge University Press. pp. 22–24. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780521565189</bdi>.</cite>

</li>

<li id="cite_note-147"><a href="#cite_ref-147">^</a> <cite id="CITEREFJohnstonRichman1997" class="citation book cs1">Johnston, Bernard L.; Richman, Fred (1997). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=koUfrlgsmUcC&pg=PA44">Numbers and Symmetry: An Introduction to Algebra</a>. CRC Press. p. 44. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780849303012</bdi>.</cite>

</li>

<li id="cite_note-148"><a href="#cite_ref-148">^</a> <cite id="CITEREFAdamsGoldstein1976" class="citation book cs1">Adams, William W.; Goldstein, Larry Joel (1976). <a rel="nofollow" class="external text" href="https://archive.org/details/introductiontonu0000adam">Introduction to Number Theory</a>. Prentice-Hall. Exercise 24, p. 205. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780134912820</bdi>. <q>State and prove an analogue of the Chinese remainder theorem for the Gaussian integers.</q></cite>

</li>

<li id="cite_note-149"><a href="#cite_ref-149">^</a> <a href="#CITEREFStark1978">Stark 1978</a>, p. 290

</li>

<li id="cite_note-150"><a href="#cite_ref-150">^</a> <a href="#CITEREFCohn1980">Cohn 1980</a>, pp. 104–105

</li>

<li id="cite_note-151"><a href="#cite_ref-151">^</a> <cite id="CITEREFLauritzen2003" class="citation book cs1">Lauritzen, Niels (2003). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=BdAbcje-TZUC&pg=PA130">Concrete Abstract Algebra: From Numbers to Gröbner Bases</a>. Cambridge University Press. p. 130. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780521534109</bdi>.</cite>

</li>

<li id="cite_note-152"><a href="#cite_ref-152">^</a> <a href="#CITEREFLauritzen2003">Lauritzen (2003)</a>, p. 132

</li>

<li id="cite_note-153"><a href="#cite_ref-153">^</a> <a href="#CITEREFLauritzen2003">Lauritzen (2003)</a>, p. 161

</li>

<li id="cite_note-sharpe-154">^ <a href="#cite_ref-sharpe_154-0">a</a> <a href="#cite_ref-sharpe_154-1">b</a> <cite id="CITEREFSharpe1987" class="citation book cs1">Sharpe, David (1987). <a rel="nofollow" class="external text" href="https://archive.org/details/ringsfactorizati0000shar">Rings and Factorization</a>. Cambridge University Press. p. <a rel="nofollow" class="external text" href="https://archive.org/details/ringsfactorizati0000shar/page/55">55</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780521337182</bdi>.</cite>

</li>

<li id="cite_note-155"><a href="#cite_ref-155">^</a> <a href="#CITEREFSharpe1987">Sharpe (1987)</a>, p. 52

</li>

<li id="cite_note-156"><a href="#cite_ref-156">^</a> <a href="#CITEREFLauritzen2003">Lauritzen (2003)</a>, p. 131

</li>

<li id="cite_note-157"><a href="#cite_ref-157">^</a> <cite id="CITEREFLamé1847" class="citation journal cs1 cs1-prop-foreign-lang-source"><a href="Gabriel_Lam%C3%A9" title="Gabriel Lamé">Lamé, G.</a> (1847). "Mémoire sur la résolution, en nombres complexes, de l'équation An + Bn + Cn = 0". J. Math. Pures Appl. (in French). 12: 172–184.</cite>

</li>

<li id="cite_note-158"><a href="#cite_ref-158">^</a> <cite id="CITEREFEdwards2000" class="citation book cs1"><a href="Harold_Edwards_(mathematician)" title="Harold Edwards (mathematician)">Edwards, H.</a> (2000). Fermat's last theorem: a genetic introduction to algebraic number theory. Springer. p. 76.</cite>

</li>

<li id="cite_note-159"><a href="#cite_ref-159">^</a> <a href="#CITEREFCohn1980">Cohn 1980</a>, pp. 104–110

</li>

<li id="cite_note-160"><a href="#cite_ref-160">^</a> <cite id="CITEREFLeVeque2002" class="citation book cs1"><a href="William_J._LeVeque" title="William J. LeVeque">LeVeque, W. J.</a> (2002) [1956]. <a rel="nofollow" class="external text" href="https://archive.org/details/topicsinnumberth0000leve">Topics in Number Theory, Volumes I and II</a>. New York: Dover Publications. pp. II:57, 81. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-486-42539-9</bdi>. <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:1009.11001">1009.11001</a>.</cite>

</li>

<li id="cite_note-Clark_1994-161">^ <a href="#cite_ref-Clark_1994_161-0">a</a> <a href="#cite_ref-Clark_1994_161-1">b</a> <cite id="CITEREFClark1994" class="citation journal cs1">Clark, D. A. (1994). <a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF02567617">"A quadratic field which is Euclidean but not norm-Euclidean"</a>. Manuscripta Mathematica. 83 (1): 327–330. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF02567617">10.1007/BF02567617</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:895185">895185</a>. <a href="Zbl_(identifier)" class="mw-redirect" title="Zbl (identifier)">Zbl</a> <a rel="nofollow" class="external text" href="https://zbmath.org/?format=complete&q=an:0817.11047">0817.11047</a>.</cite>

</li>

<li id="cite_note-bgv-162">^ <a href="#cite_ref-bgv_162-0">a</a> <a href="#cite_ref-bgv_162-1">b</a> <a href="#cite_ref-bgv_162-2">c</a> <a href="#CITEREFBuesoGómez-TorrecillasVerschoren2003">Bueso, Gómez-Torrecillas & Verschoren (2003)</a>; see pp. 37-38 for non-commutative extensions of the Euclidean algorithm and Corollary 4.35, p. 40, for more examples of noncommutative rings to which they apply.

</li>

<li id="cite_note-entgtrg-163">^ <a href="#cite_ref-entgtrg_163-0">a</a> <a href="#cite_ref-entgtrg_163-1">b</a> <cite id="CITEREFDavidoffSarnakValette2003" class="citation book cs1"><a href="Giuliana_Davidoff" title="Giuliana Davidoff">Davidoff, Giuliana</a>; Sarnak, Peter; Valette, Alain (2003). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=AlvfFDJOGZ8C&pg=PA59">"2.6 The Arithmetic of Integer Quaternions"</a>. <a href="Elementary_Number_Theory%2C_Group_Theory_and_Ramanujan_Graphs" title="Elementary Number Theory, Group Theory and Ramanujan Graphs">Elementary Number Theory, Group Theory and Ramanujan Graphs</a>. London Mathematical Society Student Texts. Vol. 55. Cambridge University Press. pp. 59–70. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780521531436</bdi>.</cite>

</li>

<li id="cite_note-164"><a href="#cite_ref-164">^</a> <cite id="CITEREFRibenboim2001" class="citation book cs1">Ribenboim, Paulo (2001). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=u5443xdaNZcC&pg=PA104">Classical Theory of Algebraic Numbers</a>. Universitext. Springer-Verlag. p. 104. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780387950709</bdi>.</cite>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="Bibliography">Bibliography</h2></div>

<ul><li><cite id="CITEREFBuesoGómez-TorrecillasVerschoren2003" class="citation book cs1">Bueso, José; Gómez-Torrecillas, José; Verschoren, Alain (2003). Algorithmic Methods in Non-Commutative Algebra: Applications to Quantum Groups. Mathematical Modelling: Theory and Applications. Vol. 17. Kluwer Academic Publishers, Dordrecht. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-94-017-0285-0">10.1007/978-94-017-0285-0</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>1-4020-1402-3</bdi>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2006329">2006329</a>.</cite></li>

<li><cite id="CITEREFCohen1993" class="citation book cs1"><a href="Henri_Cohen_(number_theorist)" title="Henri Cohen (number theorist)">Cohen, H.</a> (1993). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=hXGr-9l1DXcC">A Course in Computational Algebraic Number Theory</a>. New York: Springer-Verlag. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-387-55640-0</bdi>.</cite></li>

<li><cite id="CITEREFCohn1980" class="citation book cs1">Cohn, H. (1980). <a rel="nofollow" class="external text" href="https://archive.org/details/Cohn_Harvey_-_Advanced_Number_Theory/mode/2up">Advanced Number Theory</a>. New York: Dover. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-486-64023-X</bdi>.</cite></li>

<li><cite id="CITEREFCoxLittleO'Shea1997" class="citation book cs1"><a href="David_A._Cox" title="David A. Cox">Cox, D.</a>; Little, J.; <a href="Donal_O'Shea" title="Donal O'Shea">O'Shea, D.</a> (1997). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=7eLkq0wQytAC">Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra</a> (2nd ed.). Springer-Verlag. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-387-94680-2</bdi>.</cite></li>

<li><cite id="CITEREFCrandallPomerance2001" class="citation book cs1"><a href="Richard_Crandall" title="Richard Crandall">Crandall, R.</a>; <a href="Carl_Pomerance" title="Carl Pomerance">Pomerance, C.</a> (2001). Prime Numbers: A Computational Perspective (1st ed.). New York: Springer-Verlag. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-387-94777-9</bdi>.</cite></li>

<li><cite id="CITEREFLejeune_Dirichlet1894" class="citation book cs1 cs1-prop-foreign-lang-source"><a href="Peter_Gustav_Lejeune_Dirichlet" title="Peter Gustav Lejeune Dirichlet">Lejeune Dirichlet, P. G.</a> (1894). <a href="Richard_Dedekind" title="Richard Dedekind">Dedekind, Richard</a> (ed.). <a rel="nofollow" class="external text" href="https://archive.org/details/vorlesungenberz02dirigoog">Vorlesungen über Zahlentheorie (Lectures on Number Theory)</a> (in German). Braunschweig: Vieweg. <a href="LCCN_(identifier)" class="mw-redirect" title="LCCN (identifier)">LCCN</a> <a rel="nofollow" class="external text" href="https://lccn.loc.gov/03005859">03005859</a>. <a href="OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/490186017">490186017</a>.</cite>. See also <a href="Vorlesungen_%C3%BCber_Zahlentheorie" title="Vorlesungen über Zahlentheorie">Vorlesungen über Zahlentheorie</a></li>

<li><cite id="CITEREFKnuth1997" class="citation book cs1"><a href="Donald_Knuth" title="Donald Knuth">Knuth, D. E.</a> (1997). <a href="The_Art_of_Computer_Programming" title="The Art of Computer Programming">The Art of Computer Programming</a>, Volume 2: Seminumerical Algorithms (3rd ed.). Addison–Wesley. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-201-89684-2</bdi>.</cite></li>

<li><cite id="CITEREFLeVeque1996" class="citation book cs1"><a href="William_J._LeVeque" title="William J. LeVeque">LeVeque, W. J.</a> (1996) [1977]. Fundamentals of Number Theory. New York: Dover. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-486-68906-9</bdi>.</cite></li>

<li><cite id="CITEREFMollin2008" class="citation book cs1">Mollin, R. A. (2008). Fundamental Number Theory with Applications (2nd ed.). Boca Raton: Chapman & Hall/CRC. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4200-6659-3</bdi>.</cite></li>

<li><cite id="CITEREFOre1948" class="citation book cs1"><a href="%C3%98ystein_Ore" title="Øystein Ore">Ore, O.</a> (1948). <a rel="nofollow" class="external text" href="https://archive.org/details/numbertheoryitsh00ore">Number Theory and Its History</a>. New York: McGraw–Hill.</cite></li>

<li><cite id="CITEREFRosen2000" class="citation book cs1">Rosen, K. H. (2000). Elementary Number Theory and its Applications (4th ed.). Reading, MA: Addison–Wesley. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-201-87073-8</bdi>.</cite></li>

<li><cite id="CITEREFSchroeder2005" class="citation book cs1"><a href="Manfred_R._Schroeder" title="Manfred R. Schroeder">Schroeder, M.</a> (2005). Number Theory in Science and Communication (4th ed.). Springer-Verlag. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-387-15800-6</bdi>.</cite></li>

<li><cite id="CITEREFStark1978" class="citation book cs1"><a href="Harold_Stark" title="Harold Stark">Stark, H.</a> (1978). <a rel="nofollow" class="external text" href="https://archive.org/details/introductiontonu00star_0">An Introduction to Number Theory</a>. MIT Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-262-69060-8</bdi>.</cite></li>

<li><cite id="CITEREFStillwell1997" class="citation book cs1"><a href="John_Stillwell" title="John Stillwell">Stillwell, J.</a> (1997). Numbers and Geometry. New York: Springer-Verlag. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-387-98289-2</bdi>.</cite></li>

<li><cite id="CITEREFStillwell2003" class="citation book cs1">Stillwell, J. (2003). Elements of Number Theory. New York: Springer-Verlag. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-387-95587-9</bdi>.</cite></li>

<li><cite id="CITEREFTattersall2005" class="citation book cs1">Tattersall, J. J. (2005). Elementary Number Theory in Nine Chapters. Cambridge: <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-85014-8</bdi>.</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://www.math.sc.edu/~sumner/numbertheory/euclidean/euclidean.html">Demonstrations of Euclid's algorithm</a></li>

<li><cite id="CITEREFWeisstein" class="citation web cs1"><a href="Eric_W._Weisstein" title="Eric W. Weisstein">Weisstein, Eric W.</a> <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/EuclideanAlgorithm.html">"Euclidean Algorithm"</a>. <a href="MathWorld" title="MathWorld">MathWorld</a>.</cite></li>

<li><a rel="nofollow" class="external text" href="http://www.cut-the-knot.org/blue/Euclid.shtml">Euclid's Algorithm</a> at <a href="Cut-the-knot" class="mw-redirect" title="Cut-the-knot">cut-the-knot</a></li>

<li><a rel="nofollow" class="external text" href="https://planetmath.org/EuclidsAlgorithm">Euclid's algorithm</a> at <a href="PlanetMath" title="PlanetMath">PlanetMath</a>.</li>

<li><a rel="nofollow" class="external text" href="http://www.mathpages.com/home/kmath384.htm">The Euclidean Algorithm</a> at MathPages</li>

<li><a rel="nofollow" class="external text" href="http://www.cut-the-knot.org/blue/EuclidAlg.shtml">Euclid's Game</a> at <a href="Cut-the-knot" class="mw-redirect" title="Cut-the-knot">cut-the-knot</a></li>

<li><a rel="nofollow" class="external text" href="http://plus.maths.org/issue40/features/wardhaugh/index.html">Music and Euclid's algorithm</a></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Number-theoretic_algorithms413" style="padding:3px"><table class="nowraplinks mw-collapsible uncollapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Number-theoretic_algorithms413" style="font-size:114%;margin:0 4em"><a href="Number_theory" title="Number theory">Number-theoretic</a> <a href="Algorithm" title="Algorithm">algorithms</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Primality_test" title="Primality test">Primality tests</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Baillie%E2%80%93PSW_primality_test" title="Baillie–PSW primality test">Baillie–PSW</a></li>

<li><a href="Elliptic_curve_primality" title="Elliptic curve primality">Elliptic curve</a></li>

<li><a href="Pocklington_primality_test" title="Pocklington primality test">Pocklington</a></li>

<li><a href="Fermat_primality_test" title="Fermat primality test">Fermat</a></li>

<li><a href="Lucas_primality_test" title="Lucas primality test">Lucas</a></li>

<li><a href="Lucas%E2%80%93Lehmer_primality_test" title="Lucas–Lehmer primality test">Lucas–Lehmer</a></li>

<li><a href="Lucas%E2%80%93Lehmer%E2%80%93Riesel_test" title="Lucas–Lehmer–Riesel test">Lucas–Lehmer–Riesel</a></li>

<li><a href="Proth's_theorem" title="Proth's theorem">Proth's theorem</a></li>

<li><a href="P%C3%A9pin's_test" title="Pépin's test">Pépin's</a></li>

<li><a href="Quadratic_Frobenius_test" title="Quadratic Frobenius test">Quadratic Frobenius</a></li>

<li><a href="Solovay%E2%80%93Strassen_primality_test" title="Solovay–Strassen primality test">Solovay–Strassen</a></li>

<li><a href="Miller%E2%80%93Rabin_primality_test" title="Miller–Rabin primality test">Miller–Rabin</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Generating_primes" class="mw-redirect" title="Generating primes">Prime-generating</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Sieve_of_Atkin" title="Sieve of Atkin">Sieve of Atkin</a></li>

<li><a href="Sieve_of_Eratosthenes" title="Sieve of Eratosthenes">Sieve of Eratosthenes</a></li>

<li><a href="Sieve_of_Pritchard" title="Sieve of Pritchard">Sieve of Pritchard</a></li>

<li><a href="Sieve_of_Sundaram" title="Sieve of Sundaram">Sieve of Sundaram</a></li>

<li><a href="Wheel_factorization" title="Wheel factorization">Wheel factorization</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Integer_factorization" title="Integer factorization">Integer factorization</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Continued_fraction_factorization" title="Continued fraction factorization">Continued fraction (CFRAC)</a></li>

<li><a href="Dixon's_factorization_method" title="Dixon's factorization method">Dixon's</a></li>

<li><a href="Lenstra_elliptic-curve_factorization" title="Lenstra elliptic-curve factorization">Lenstra elliptic curve (ECM)</a></li>

<li><a href="Euler's_factorization_method" title="Euler's factorization method">Euler's</a></li>

<li><a href="Pollard's_rho_algorithm" title="Pollard's rho algorithm">Pollard's rho</a></li>

<li><a href="Quadratic_sieve" title="Quadratic sieve">Quadratic sieve (QS)</a></li>

<li><a href="General_number_field_sieve" title="General number field sieve">General number field sieve (GNFS)</a></li>

<li><a href="Special_number_field_sieve" title="Special number field sieve">Special number field sieve (SNFS)</a></li>

<li><a href="Rational_sieve" title="Rational sieve">Rational sieve</a></li>

<li><a href="Fermat's_factorization_method" title="Fermat's factorization method">Fermat's</a></li>

<li><a href="Shanks's_square_forms_factorization" title="Shanks's square forms factorization">Shanks's square forms</a></li>

<li><a href="Trial_division" title="Trial division">Trial division</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Multiplication_algorithm" title="Multiplication algorithm">Multiplication</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Ancient_Egyptian_multiplication" title="Ancient Egyptian multiplication">Ancient Egyptian</a></li>

<li><a href="Karatsuba_algorithm" title="Karatsuba algorithm">Karatsuba</a></li>

<li><a href="Sch%C3%B6nhage%E2%80%93Strassen_algorithm" title="Schönhage–Strassen algorithm">Schönhage–Strassen</a></li>

<li><a href="F%C3%BCrer's_algorithm" class="mw-redirect" title="Fürer's algorithm">Fürer's</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Euclidean_division" title="Euclidean division">Euclidean</a> <a href="Division_algorithm" title="Division algorithm">division</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Binary_division" class="mw-redirect" title="Binary division">Binary</a></li>

<li><a href="Chunking_(division)" title="Chunking (division)">Chunking</a></li>

<li><a href="Fourier_division" title="Fourier division">Fourier</a></li>

<li><a href="Goldschmidt_division" class="mw-redirect" title="Goldschmidt division">Goldschmidt</a></li>

<li><a href="Newton%E2%80%93Raphson_division" class="mw-redirect" title="Newton–Raphson division">Newton-Raphson</a></li>

<li><a href="Short_division" title="Short division">Short</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Discrete_logarithm" title="Discrete logarithm">Discrete logarithm</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Baby-step_giant-step" title="Baby-step giant-step">Baby-step giant-step</a></li>

<li><a href="Pollard's_rho_algorithm_for_logarithms" title="Pollard's rho algorithm for logarithms">Pollard rho</a></li>

<li><a href="Pollard's_kangaroo_algorithm" title="Pollard's kangaroo algorithm">Pollard kangaroo</a></li>

<li><a href="Pohlig%E2%80%93Hellman_algorithm" title="Pohlig–Hellman algorithm">Pohlig–Hellman</a></li>

<li><a href="Index_calculus_algorithm" title="Index calculus algorithm">Index calculus</a></li>

<li><a href="Function_field_sieve" title="Function field sieve">Function field sieve</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Greatest_common_divisor" title="Greatest common divisor">Greatest common divisor</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Binary_GCD_algorithm" title="Binary GCD algorithm">Binary</a></li>

<li><a href="Extended_Euclidean_algorithm" title="Extended Euclidean algorithm">Extended Euclidean</a></li>

<li><a href="Lehmer's_GCD_algorithm" title="Lehmer's GCD algorithm">Lehmer's</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quadratic_residue" title="Quadratic residue">Modular square root</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Cipolla's_algorithm" title="Cipolla's algorithm">Cipolla</a></li>

<li><a href="Pocklington's_algorithm" title="Pocklington's algorithm">Pocklington's</a></li>

<li><a href="Tonelli%E2%80%93Shanks_algorithm" title="Tonelli–Shanks algorithm">Tonelli–Shanks</a></li>

<li><a href="Berlekamp%E2%80%93Rabin_algorithm" title="Berlekamp–Rabin algorithm">Berlekamp</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other algorithms</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Chakravala_method" title="Chakravala method">Chakravala</a></li>

<li><a href="Cornacchia's_algorithm" title="Cornacchia's algorithm">Cornacchia</a></li>

<li><a href="Exponentiation_by_squaring" title="Exponentiation by squaring">Exponentiation by squaring</a></li>

<li><a href="Integer_square_root" title="Integer square root">Integer square root</a></li>

<li><a href="Integer_relation_algorithm" title="Integer relation algorithm">Integer relation</a> (<a href="Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm" title="Lenstra–Lenstra–Lovász lattice basis reduction algorithm">LLL</a>; <a href="Korkine%E2%80%93Zolotarev_lattice_basis_reduction_algorithm" title="Korkine–Zolotarev lattice basis reduction algorithm">KZ</a>)</li>

<li><a href="Modular_exponentiation" title="Modular exponentiation">Modular exponentiation</a></li>

<li><a href="Montgomery_reduction" class="mw-redirect" title="Montgomery reduction">Montgomery reduction</a></li>

<li><a href="Schoof's_algorithm" title="Schoof's algorithm">Schoof</a></li>

<li><a href="Trachtenberg_system" title="Trachtenberg system">Trachtenberg system</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow hlist" colspan="2"><div>

<ul><li>Italics indicate that algorithm is for numbers of special forms</li></ul>

</div></td></tr></tbody></table></div>

<div class="navbox-styles"></div><div role="navigation" class="navbox" aria-labelledby="Ancient_Greek_mathematics550" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Ancient_Greek_mathematics550" style="font-size:114%;margin:0 4em"><a href="Ancient_Greek_mathematics" title="Ancient Greek mathematics">Ancient Greek mathematics</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="List_of_Greek_mathematicians" title="List of Greek mathematicians">Mathematicians</a> <a href="Timeline_of_ancient_Greek_mathematicians" title="Timeline of ancient Greek mathematicians">(timeline)</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Anaxagoras" title="Anaxagoras">Anaxagoras</a></li>

<li><a href="Anthemius_of_Tralles" title="Anthemius of Tralles">Anthemius</a></li>

<li><a href="Apollonius_of_Perga" title="Apollonius of Perga">Apollonius</a></li>

<li><a href="Archimedes" title="Archimedes">Archimedes</a></li>

<li><a href="Archytas" title="Archytas">Archytas</a></li>

<li><a href="Aristaeus_the_Elder" title="Aristaeus the Elder">Aristaeus the Elder</a></li>

<li><a href="Aristarchus_of_Samos" title="Aristarchus of Samos">Aristarchus</a></li>

<li><a href="Autolycus_of_Pitane" title="Autolycus of Pitane">Autolycus</a></li>

<li><a href="Bryson_of_Heraclea" title="Bryson of Heraclea">Bryson</a></li>

<li><a href="Callippus" title="Callippus">Callippus</a></li>

<li><a href="Carpus_of_Antioch" title="Carpus of Antioch">Carpus</a></li>

<li><a href="Chrysippus" title="Chrysippus">Chrysippus</a></li>

<li><a href="Cleomedes" title="Cleomedes">Cleomedes</a></li>

<li><a href="Conon_of_Samos" title="Conon of Samos">Conon</a></li>

<li><a href="Ctesibius" title="Ctesibius">Ctesibius</a></li>

<li><a href="Democritus" title="Democritus">Democritus</a></li>

<li><a href="Dicaearchus" title="Dicaearchus">Dicaearchus</a></li>

<li><a href="Dinostratus" title="Dinostratus">Dinostratus</a></li>

<li><a href="Diocles_(mathematician)" title="Diocles (mathematician)">Diocles</a></li>

<li><a href="Dionysodorus" title="Dionysodorus">Dionysodorus of Caunus</a></li>

<li><a href="Dionysodorus_of_Amisene" title="Dionysodorus of Amisene">Dionysodorus of Amisene</a></li>

<li><a href="Diophantus" title="Diophantus">Diophantus</a></li>

<li><a href="Domninus_of_Larissa" title="Domninus of Larissa">Domninus</a></li>

<li><a href="Eratosthenes" title="Eratosthenes">Eratosthenes</a></li>

<li><a href="Euclid" title="Euclid">Euclid</a></li>

<li><a href="Eudemus_of_Rhodes" title="Eudemus of Rhodes">Eudemus</a></li>

<li><a href="Eudoxus_of_Cnidus" title="Eudoxus of Cnidus">Eudoxus</a></li>

<li><a href="Eutocius_of_Ascalon" title="Eutocius of Ascalon">Eutocius</a></li>

<li><a href="Geminus" title="Geminus">Geminus</a></li>

<li><a href="Heliodorus_of_Larissa" title="Heliodorus of Larissa">Heliodorus</a></li>

<li><a href="Hero_of_Alexandria" title="Hero of Alexandria">Heron</a></li>

<li><a href="Hipparchus" title="Hipparchus">Hipparchus</a></li>

<li><a href="Hippasus" title="Hippasus">Hippasus</a></li>

<li><a href="Hippias" title="Hippias">Hippias</a></li>

<li><a href="Hippocrates_of_Chios" title="Hippocrates of Chios">Hippocrates</a></li>

<li><a href="Hypatia" title="Hypatia">Hypatia</a></li>

<li><a href="Hypsicles" title="Hypsicles">Hypsicles</a></li>

<li><a href="Isidore_of_Miletus" title="Isidore of Miletus">Isidore of Miletus</a></li>

<li><a href="Marinus_of_Neapolis" title="Marinus of Neapolis">Marinus</a></li>

<li><a href="Menaechmus" title="Menaechmus">Menaechmus</a></li>

<li><a href="Menelaus_of_Alexandria" title="Menelaus of Alexandria">Menelaus</a></li>

<li><a href="Metrodorus_(grammarian)" title="Metrodorus (grammarian)">Metrodorus</a></li>

<li><a href="Nicomachus" title="Nicomachus">Nicomachus</a></li>

<li><a href="Nicomedes_(mathematician)" title="Nicomedes (mathematician)">Nicomedes</a></li>

<li><a href="Nicoteles_of_Cyrene" title="Nicoteles of Cyrene">Nicoteles</a></li>

<li><a href="Oenopides" title="Oenopides">Oenopides</a></li>

<li><a href="Pandrosion" title="Pandrosion">Pandrosion</a></li>

<li><a href="Pappus_of_Alexandria" title="Pappus of Alexandria">Pappus</a></li>

<li><a href="Perseus_(geometer)" title="Perseus (geometer)">Perseus</a></li>

<li><a href="Philolaus" title="Philolaus">Philolaus</a></li>

<li><a href="Philon" title="Philon">Philon</a></li>

<li><a href="Philonides_of_Laodicea" title="Philonides of Laodicea">Philonides</a></li>

<li><a href="Porphyry_of_Tyre" title="Porphyry of Tyre">Porphyry of Tyre</a></li>

<li><a href="Posidonius" title="Posidonius">Posidonius</a></li>

<li><a href="Proclus" title="Proclus">Proclus</a></li>

<li><a href="Ptolemy" title="Ptolemy">Ptolemy</a></li>

<li><a href="Pythagoras" title="Pythagoras">Pythagoras</a></li>

<li><a href="Serenus_of_Antino%C3%B6polis" title="Serenus of Antinoöpolis">Serenus</a></li>

<li><a href="Sosigenes_of_Alexandria" class="mw-redirect" title="Sosigenes of Alexandria">Sosigenes</a></li>

<li><a href="Sporus_of_Nicaea" title="Sporus of Nicaea">Sporus</a></li>

<li><a href="Thales_of_Miletus" title="Thales of Miletus">Thales</a></li>

<li><a href="Theaetetus_(mathematician)" title="Theaetetus (mathematician)">Theaetetus</a></li>

<li><a href="Theodorus_of_Cyrene" title="Theodorus of Cyrene">Theodorus</a></li>

<li><a href="Theodosius_of_Bithynia" title="Theodosius of Bithynia">Theodosius</a></li>

<li><a href="Theon_of_Alexandria" title="Theon of Alexandria">Theon of Alexandria</a></li>

<li><a href="Theon_of_Smyrna" title="Theon of Smyrna">Theon of Smyrna</a></li>

<li><a href="Thymaridas" title="Thymaridas">Thymaridas</a></li>

<li><a href="Xenocrates" title="Xenocrates">Xenocrates</a></li>

<li><a href="Zeno_of_Sidon" title="Zeno of Sidon">Zeno of Sidon</a></li>

<li><a href="Zenodorus_(mathematician)" title="Zenodorus (mathematician)">Zenodorus</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Treatises</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Almagest" title="Almagest">Almagest</a></li>

<li><a href="Arithmetica" class="mw-redirect" title="Arithmetica">Arithmetica</a></li>

<li><a href="Apollonius_of_Perga#Conics" title="Apollonius of Perga">Conics (Apollonius)</a></li>

<li><a href="Catoptrics" title="Catoptrics">Catoptrics</a></li>

<li><a href="Data_(Euclid)" class="mw-redirect" title="Data (Euclid)">Data (Euclid)</a></li>

<li><a href="Euclid's_Elements" title="Euclid's Elements">Elements (Euclid)</a></li>

<li><a href="Little_Astronomy" title="Little Astronomy">Little Astronomy</a></li>

<li><a href="Measurement_of_a_Circle" title="Measurement of a Circle">Measurement of a Circle</a></li>

<li><a href="On_Conoids_and_Spheroids" title="On Conoids and Spheroids">On Conoids and Spheroids</a></li>

<li><a href="On_the_Sizes_and_Distances_(Aristarchus)" title="On the Sizes and Distances (Aristarchus)">On the Sizes and Distances (Aristarchus)</a></li>

<li><a href="On_Sizes_and_Distances_(Hipparchus)" title="On Sizes and Distances (Hipparchus)">On Sizes and Distances (Hipparchus)</a></li>

<li><a href="Autolycus_of_Pitane" title="Autolycus of Pitane">On the Moving Sphere (Autolycus)</a></li>

<li><a href="Euclid's_Optics" title="Euclid's Optics">Optics (Euclid)</a></li>

<li><a href="On_Spirals" title="On Spirals">On Spirals</a></li>

<li><a href="On_the_Sphere_and_Cylinder" title="On the Sphere and Cylinder">On the Sphere and Cylinder</a></li>

<li><a href="Ostomachion" title="Ostomachion">Ostomachion</a></li>

<li><a href="Euclid's_Phaenomena" title="Euclid's Phaenomena">Phaenomena (Euclid)</a></li>

<li><a href="Planisphaerium" title="Planisphaerium">Planisphaerium</a></li>

<li><a href="Theodosius'_Spherics" title="Theodosius' Spherics">Spherics (Theodosius)</a></li>

<li><a href="Menelaus_of_Alexandria" title="Menelaus of Alexandria">Spherics (Menelaus)</a></li>

<li><a href="The_Quadrature_of_the_Parabola" class="mw-redirect" title="The Quadrature of the Parabola">The Quadrature of the Parabola</a></li>

<li><a href="The_Sand_Reckoner" title="The Sand Reckoner">The Sand Reckoner</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Concepts and definitions</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Chord_(geometry)" title="Chord (geometry)">Chord</a></li>

<li><a href="Circles_of_Apollonius" title="Circles of Apollonius">Circles of Apollonius</a>

<ul><li><a href="Apollonian_circles" title="Apollonian circles">Apollonian circles</a></li>

<li><a href="Apollonian_gasket" title="Apollonian gasket">Apollonian gasket</a></li>

<li><a href="Problem_of_Apollonius" title="Problem of Apollonius">Problem of Apollonius</a></li></ul></li>

<li><a href="Commensurability_(mathematics)" title="Commensurability (mathematics)">Commensurability</a></li>

<li><a href="Diophantine_equation" title="Diophantine equation">Diophantine equation</a></li>

<li><a href="Euclidean_geometry" title="Euclidean geometry">Euclidean geometry</a></li>

<li><a href="Golden_ratio" title="Golden ratio">Golden ratio</a></li>

<li><a href="Lune_of_Hippocrates" title="Lune of Hippocrates">Lune of Hippocrates</a></li>

<li><a href="Method_of_exhaustion" title="Method of exhaustion">Method of exhaustion</a></li>

<li><a href="Parallel_postulate" title="Parallel postulate">Parallel postulate</a></li>

<li><a href="Platonic_solid" title="Platonic solid">Platonic solid</a></li>

<li><a href="Regular_polygon" title="Regular polygon">Regular polygon</a></li>

<li><a href="Straightedge_and_compass_construction" title="Straightedge and compass construction">Straightedge and compass construction</a>

<ul><li><a href="Angle_trisection" title="Angle trisection">Angle trisection</a></li>

<li><a href="Doubling_the_cube" title="Doubling the cube">Doubling the cube</a></li>

<li><a href="Squaring_the_circle" title="Squaring the circle">Squaring the circle</a></li>

<li><a href="Quadratrix_of_Hippias" title="Quadratrix of Hippias">Quadratrix of Hippias</a></li>

<li><a href="Neusis_construction" title="Neusis construction">Neusis construction</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Results</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="In_Elements37" scope="row" class="navbox-group" style="width:1%">In <a href="Euclid's_elements" class="mw-redirect" title="Euclid's elements">Elements</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Angle_bisector_theorem" title="Angle bisector theorem">Angle bisector theorem</a></li>

<li><a href="Exterior_angle_theorem" title="Exterior angle theorem">Exterior angle theorem</a></li>

<li><a href="Euclid's_theorem" title="Euclid's theorem">Euclid's theorem</a></li>

<li><a href="Geometric_mean_theorem" title="Geometric mean theorem">Geometric mean theorem</a></li>

<li><a href="Hinge_theorem" title="Hinge theorem">Hinge theorem</a></li>

<li><a href="Inscribed_angle_theorem" class="mw-redirect" title="Inscribed angle theorem">Inscribed angle theorem</a></li>

<li><a href="Intercept_theorem" title="Intercept theorem">Intercept theorem</a></li>

<li><a href="Intersecting_chords_theorem" title="Intersecting chords theorem">Intersecting chords theorem</a></li>

<li><a href="Intersecting_secants_theorem" title="Intersecting secants theorem">Intersecting secants theorem</a></li>

<li><a href="Law_of_cosines" title="Law of cosines">Law of cosines</a></li>

<li><a href="Pons_asinorum" title="Pons asinorum">Pons asinorum</a></li>

<li><a href="Pythagorean_theorem" title="Pythagorean theorem">Pythagorean theorem</a></li>

<li><a href="Tangent-secant_theorem" class="mw-redirect" title="Tangent-secant theorem">Tangent-secant theorem</a></li>

<li><a href="Thales's_theorem" title="Thales's theorem">Thales's theorem</a></li>

<li><a href="Theorem_of_the_gnomon" title="Theorem of the gnomon">Theorem of the gnomon</a></li></ul>

</div></td></tr></tbody></table><div>

<ul><li><a href="Apollonius's_theorem" title="Apollonius's theorem">Apollonius's theorem</a></li>

<li><a href="Aristarchus's_inequality" title="Aristarchus's inequality">Aristarchus's inequality</a></li>

<li><a href="Heron's_formula" title="Heron's formula">Heron's formula</a></li>

<li><a href="Law_of_sines" title="Law of sines">Law of sines</a></li>

<li><a href="Menelaus's_theorem" title="Menelaus's theorem">Menelaus's theorem</a></li>

<li><a href="Pappus's_area_theorem" title="Pappus's area theorem">Pappus's area theorem</a></li>

<li><a href="Diophantus_II.VIII" title="Diophantus II.VIII">Problem II.8 of Arithmetica</a></li>

<li><a href="Ptolemy's_inequality" title="Ptolemy's inequality">Ptolemy's inequality</a></li>

<li><a href="Ptolemy's_table_of_chords" title="Ptolemy's table of chords">Ptolemy's table of chords</a></li>

<li><a href="Ptolemy's_theorem" title="Ptolemy's theorem">Ptolemy's theorem</a></li>

<li><a href="Spiral_of_Theodorus" title="Spiral of Theodorus">Spiral of Theodorus</a></li></ul></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Centers/Schools</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Cyrene%2C_Libya" title="Cyrene, Libya">Cyrene</a></li>

<li><a href="Platonic_Academy" title="Platonic Academy">Platonic Academy</a></li>

<li><a href="Pythagoreanism" title="Pythagoreanism">Pythagoreanism</a></li>

<li><a href="School_of_Chios" title="School of Chios">School of Chios</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Related</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><td colspan="2" class="navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Ancient_Greek_astronomy" title="Ancient Greek astronomy">Ancient Greek astronomy</a></li>

<li><a href="Attic_numerals" title="Attic numerals">Attic numerals</a></li>

<li><a href="Greek_numerals" title="Greek numerals">Greek numerals</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">History of</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="A_History_of_Greek_Mathematics" title="A History of Greek Mathematics">A History of Greek Mathematics</a>

<ul><li>by <a href="Thomas_Heath_(classicist)" title="Thomas Heath (classicist)">Thomas Heath</a></li></ul></li>

<li><a href="Archimedes_Palimpsest" title="Archimedes Palimpsest">Archimedes Palimpsest</a></li>

<li><a href="History_of_algebra" title="History of algebra">algebra</a>

<ul><li><a href="Timeline_of_algebra" title="Timeline of algebra">timeline</a></li></ul></li>

<li><a href="History_of_arithmetic" class="mw-redirect" title="History of arithmetic">arithmetic</a>

<ul><li><a href="Timeline_of_numerals_and_arithmetic" title="Timeline of numerals and arithmetic">timeline</a></li></ul></li>

<li><a href="History_of_calculus" title="History of calculus">calculus</a>

<ul><li><a href="Timeline_of_calculus_and_mathematical_analysis" title="Timeline of calculus and mathematical analysis">timeline</a></li></ul></li>

<li><a href="History_of_geometry" title="History of geometry">geometry</a>

<ul><li><a href="Timeline_of_geometry" title="Timeline of geometry">timeline</a></li></ul></li>

<li><a href="History_of_logic" title="History of logic">logic</a>

<ul><li><a href="Timeline_of_mathematical_logic" title="Timeline of mathematical logic">timeline</a></li></ul></li>

<li><a href="History_of_mathematics" title="History of mathematics">mathematics</a>

<ul><li><a href="Timeline_of_mathematics" title="Timeline of mathematics">timeline</a></li></ul></li>

<li><a href="History_of_numbers" class="mw-redirect" title="History of numbers">numbers</a>

<ul><li><a href="Prehistoric_counting" class="mw-redirect" title="Prehistoric counting">prehistoric counting</a></li></ul></li>

<li><a href="History_of_ancient_numeral_systems" title="History of ancient numeral systems">numeral systems</a>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other cultures</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Mathematics_in_the_medieval_Islamic_world" title="Mathematics in the medieval Islamic world">Arabian/Islamic</a></li>

<li><a href="Babylonian_mathematics" title="Babylonian mathematics">Babylonian</a></li>

<li><a href="Chinese_mathematics" title="Chinese mathematics">Chinese</a></li>

<li><a href="Ancient_Egyptian_mathematics" title="Ancient Egyptian mathematics">Egyptian</a></li>

<li><a href="Mathematics_of_the_Incas" title="Mathematics of the Incas">Incan</a></li>

<li><a href="Indian_mathematics" title="Indian mathematics">Indian</a></li>

<li><a href="Japanese_mathematics" title="Japanese mathematics">Japanese</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div> <a href="Portal%3AAncient_Greece" title="Portal:Ancient Greece">Ancient Greece portal</a> • <a href="Portal%3AMathematics" title="Portal:Mathematics">Mathematics portal</a></div></td></tr></tbody></table></div>

<div class="navbox-styles"></div><div role="navigation" class="navbox authority-control" aria-label="Navbox390" style="padding:3px"><table class="nowraplinks hlist navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">Authority control databases: National </th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><a rel="nofollow" class="external text" href="https://d-nb.info/gnd/4659898-4">Germany</a></li></ul></div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-25" href="https://en.wikipedia.org/wiki/?title=Euclidean_algorithm&oldid=1302372519">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>